CODEWITHSUNDEEP
time-complexity
Abhishek kumar
Abhishek kumar

Reputation: 43

Calculating the time complexity

Can somebody help with the time complexity of the following code:

for(i = 0; i <= n; i++)
{
   for(j = 0; j <= i; j++)
      {
         for(k = 2; k <= n; k = k^2)
              print("")
      }

a/c to me the first loop will run n times,2nd will run for(1+2+3...n) times and third for loglogn times.. but i m not sure about the answer.

Upvotes: 0

Views: 34

Answers (1)

Patrick87
Patrick87

Reputation: 28292

We start from the inside and work out. Consider the innermost loop:

for(k = 2; k <= n; k = k^2)
    print("")

How many iterations of print("") are executed? First note that n is constant. What sequence of values does k assume?

iter | k
--------
   1 | 2
   2 | 4
   3 | 16
   4 | 256

We might find a formula for this in several ways. I used guess and prove to get iter = log(log(k)) + 1. Since the loop won't execute the next iteration if the value is already bigger than n, the total number of iterations executed for n is floor(log(log(n)) + 1). We can check this with a couple of values to make sure we got this right. For n = 2, we get one iteration which is correct. For n = 5, we get two. And so on.

The next level does i + 1 iterations, where i varies from 0 to n. We must therefore compute the sum 1, 2, ..., n + 1 and that will give us the total number of iterations of the outermost and middle loop: this sum is (n + 1)(n + 2) / 2 We must multiply this by the cost of the inner loop to get the answer, (n + 1)(n + 2)(log(log(n)) + 1) / 2 to get the total cost of the snippet. The fastest-growing term in the expansion is n^2 log(log(n)) and so that is what would typically be given as asymptotic complexity.

Upvotes: 1

Related Questions