There will be exactly n iterations of the first loop.
There will be exactly n(n+1)/2 iterations of the second loop.
Inside of the second loop there is roughly 1/3 of n/2 long loops, 1/3 of j long loops and 1/3 of 2 long loops.
If we look only at the first of the three possible cases then we get (n(n+1)/2) * 1/3 * n/2 that is n*n*(n+1)/12 which is O(n^3) or even more precisely Theta(n^3)
The two additional cases don’t make much difference, they only change constants.
To conclude, in both the pessimistic and optimistic case, this code has to perform a number of iterations that is proportional to n^3.
2
solved what is the best-case / worst-case analysis for the following loop? [closed]