Hard Big O complexity for 3 loops

I try to calculate Big O complexity for this code but I always fail....

I tried to nest SUM's or to get the number of steps for each case like:

then sum all the steps together, I need help.

for (int i=1; i<=n; i*=2)

for (int j=1; j<=i; j*=2)

for(int k=1; k<=j*j; k++)

//code line with complexity code O(1)


2 Answers
2

Let's take a look at the number of times the inner loop runs: j2. But j steps along in powers of 2 up to i. i in turn steps in powers of 2 up to n. So let's "draw" a little graphic of the terms of the sum that would give us the total number of iterations:

j2

j

i

i

n

log2(n)

log2(n)

The graphic can be interpreted as follows: each value of i corresponds to a row. Each value of j is a column within that row. The number itself is the number of iterations k goes through. The values of j are the square roots of the numbers. The values of i are the square roots of the last element in each row. The sum of all the numbers is the total number of iterations.

i

j

k

j

i

Looking at the bottom row, the terms of the sum are (2z)2 = 22z for z = 1 ... log2(n). The number of times that the terms appear in the sum is modulated by the height of the column. The height for a given term is log2(n) + 1 - z (basically a count down from log2(n)).

(2z)2 = 22z

z = 1 ... log2(n)

log2(n) + 1 - z

log2(n)

So the final sum is

Here is what Wolfram Alpha has to say about evaluating the sum: http://m.wolframalpha.com/input/?i=sum+%28%28log%5B2%2C+n%5D%29+%2B+1+-+z%29%282%5E%282z%29%29%2C+z%3D1+to+log%5B2%2C+n%5D:

Cutting out all the less significant terms and constants, the result is

For the outermost loop:

sum_i in 1, 2, 4, 8, 16, ... 1, i <= n (+)

<=>

sum_i in 2^0, 2^1, 2^2, ... 1, i <= n

Let 2^I = i:

2^I = i <=> e^I log 2 = i <=> I log 2 = log i <=> I = (log i)/(log 2)

Thus, (+) is equivalent to

sum_I in 0, 1, ... 1, I <= floor((log n)/(log 2)) ~= log n (*)


Second outermost loop:

sum_j in 1, 2, 4, 8, 16, ... 1, j <= i (++)

As above, 2^I = i, and let 2^J = j. Similarly to above,
(++) is equivalent to:

sum_J in 0, 1, ... 1, J <= floor((log (2^I))/(log 2)) = floor(I/(log 2)) ~= I (**)


To touch base, only the outermost and second outermost
have now been reduced to

sum_I in 0, 1, ... ^log n sum_J in 0, 1, ...^I ...

Which is (if there would be no innermost loop) O((log n)^2)


Innermost loop is a trivial one if we can express the largest bound in terms of `n`.

sum_k in 1, 2, 3, 4, ... 1, k <= j^2 (+)

As above, let 2^J = j and note that j^2 = 2^(2J)

sum_k in 1, 2, 3, 4, ... 1, k <= 2^(2J)

Thus, k is bounded by 2^(2 max(J)) = 2^(2 max(I)) = 2^(2 log(n) ) = 2n^2 (***)


Combining (*), (**) and (***), the asymptotic complexity of the three nested loops is:

(*)

(**)

(***)

O(n^2 log^2 n)

O((n log n)^2)

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.