CODEWITHSUNDEEP
timetime-complexitycomplexity-theory
ross.c
ross.c

Reputation: 143

Time complexity for two nested for loops

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.

Upvotes: 1

Views: 235

Answers (1)

Alexandre Dupriez
Alexandre Dupriez

Reputation: 3036

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.

Upvotes: 2

Related Questions