Analyzing algorithms for time complexity

Question

I am analyzing an algorithm and I just want to know if I am on the right track.

For this algorithm, I am only counting the multiplications on the line which have *** in them.

Here's the algorithm:

1. So I am starting from the inner most line, I can see there are 2 operations there (the two multiplications).
2. Now I am looking at the 2 inner most loops, so I can tell that the p=p*20*z gets executed exactly (j) + (j-1)+(j-2)+(j-3)...1 times. This happens to be equal to j(j+1)/2.
3. So in total, since there are two multiplication, it happens 2 * (j(j+1)/2).
4. Then finally, the "i" loop happens exactly n times, so, in total, it's n(2 * (n(n+1)/2)).

That's my thought process behind this. Am I correct? Thanks.

Answer 1

Your thought process is correct. You need to replace the j term with an n (n being the largest value j can assume), but that is probably a typo.

Furthermore, you can simplify further from where you are:

n(2*(n(n+1)/2))
2*n*(n^2+n)/2
n^3+n^2

=> O(n^3)

The last step is because the n cubed term will grow at a much larger rate than the n squared term we can say it will dominate the runtime for large n. Only other point I would mention is that you should perhaps consider the store to p as an operation as well as the two multiplication, although obviously this will not change the simplified big-o runtime.

Answer 2

Computation in this particular example could be simplified if you can find out that all three loops has the same exit condition up to n:

1. i <= n
2. j <= n
3. k <= j

Basically third loop would run n iterations as well because j <= n so k <= n, this mean that complexity would be n * n * n = O(n ^ 3)