Analysis of time complexity algorithms

Question

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

For this algorithm, I only count multiplications by a string in which there is ***.

Here's the algorithm:

• So, I start with the innermost line, I see that there are two operations (two multiplications).
• Now I look through 2 of the inner majority of the contour, so I can say that p=p*20*z is executed exactly (j) + (j-1)+(j-2)+(j-3)...1 time. This turns out to be j(j+1)/2 .
• Thus, since there are two multiplications, this happens 2 * (j(j+1)/2) .
• Then, finally, the cycle "i" is executed exactly n times, so in general it is n(2 * (n(n+1)/2)) .

This is my thought process. I'm right? Thanks.

Answer 1

Your thought process is correct. You need to replace the j-term with n (n is the largest value of j that can be accepted), but this is probably a typo.

In addition, you can simplify further actions:

 n(2*(n(n+1)/2)) 2*n*(n^2+n)/2 n^3+n^2 => O(n^3) 

The last step is that the n cubic member will grow much larger than the n square, we can say that it will dominate the execution time for large n. Only another point that I would like to mention is that you should apparently consider the storage p as an operation, as well as two multiplications, although obviously this will not change the simplified long run time.

Answer 2

The calculation in this particular example can be simplified if you can find out that all three loops have the same up to n exit condition:

• i <= n
• j <= n
• k <= j

Basically, the third loop will start iterations n , because j <= n so k <= n , which means that the complexity will be n * n * n = O(n ^ 3)

Answer 3

Here's how you can methodically get the growth order of your algorithm: