Time complexity for two nested for loops

Question

This question is for revision from a past test paper just needed advice if I on the right track.

Work out the time complexity T(n) of the following piece of code in terms of number of operations for a given integer n:

for ( int k = n; k >0; k /= 3 ) {
  for ( int i = 0; i < n; i += 2 ) {
     // constant number C of elementary operations
  }
  for ( int j = 2; j < n; j = (j*j)) {
      // constant number C of elementary operations
  }
}

So I thought the outer loop would be O(logn), the first inner loop would be O(n) and the second inner loop would be O(logn). Just wanted to know if I had a rough idea and how to move forward from here.

Alexandre Dupriez · Accepted Answer · 2018-03-06 13:36:05Z

2

There was recently a question somewhat similar few days ago for which I provided a step-by-step description of complexity analysis: https://stackoverflow.com/a/49093954/926701

The outer loop is indeed O(log3(n))
The first inner loop is indeed O(n)
The second inner loop is O(log2(log2(n)))

Informally, for the second loop, with j(k) the sequence of values taken by the index j of the for loop, we can write:

j(1) = 2, j(2) = j(1)^2 = 4, j(3) = j(2)^2 = 16, ..., j(k) = j(k-1)^2 >= n 
=> j(k) = j(k-1)^2 = j(k-2)^4 = ... = j(1)^(2^k) = 2^(2^k)
=> k = log2(log2(n))

Since the number of operations in the inner loops is independent from that of the outer loop, we can multiply the complexity:

T(n) = O(log3(n) * (n + log2(log2(n))))
     = O(n.log3(n))

because log2(log2(n)) << n as n -> +Inf.

edited Mar 6, 2018 at 13:36

answered Mar 6, 2018 at 11:44

Alexandre Dupriez

3,05623 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

meowgoesthedog Over a year ago

Why is the second loop n^(1/log2(log2(n)))) instead of simply log2(log2(n))?

Alexandre Dupriez Over a year ago

Thank you for pointing the mistake out, I corrected the post.

ross.c Over a year ago

I'm sorry I don't quite get it, why do you go j(2) = j(1) ^ 2 = 4 ? how'd the 2 go into 1 ?

Alexandre Dupriez Over a year ago

@ross.c Not sure I understand your question, but j(1) is the first value assigned to j in the loop, so 2, and the next is j(1) = 2 * 2 = 4. Is this what you wanted to clarify?

ross.c Over a year ago

@AlexandreDupriez yes thats better sorry I thought for some reason it was (1) ^ 2 as in 1 * 1 so was getting confused ! thanks for the help :)

Collectives™ on Stack Overflow

Time complexity for two nested for loops

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related