CODEWITHSUNDEEP
algorithmtime-complexity
Ameen Ali
Ameen Ali

Reputation: 9

how to find this function complexity?

I got log n but it's not log n it is log(log n)
but why?


int function(int n){
  return aux(n , 2)
}

int aux(int n, int x){
  while (n<x) {
    x *= x;
  }
  return x;  
}

what is the complexity of function ?

Upvotes: 0

Views: 75

Answers (1)

Zong
Zong

Reputation: 6230

Pretty sure the loop condition is supposed to be n > x so I'll be assuming it in this answer.

First, observe the values of x:

x1 = x0 * x0
   = 2 * 2
   = 2^2
x2 = x1 * x1 
   = x0 * x0 * x0 * x0
   = 2 * 2 * 2 * 2
   = 2^4
x3 = x2 * x2
   = x1 * x1 * x1 * x1 
   = x0 * x0 * x0 * x0 * x0 * x0 * x0 * x0
   = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
   = 2^8

We see that the exponent is growing as 2^t where t is the number of iterations in the loop so we can obtain the closed form equation for x:

x = 2^(2^t)

Then we can solve for the number of iterations t:

n > x
=> n > 2^(2^t)
=> log(n) > 2^t
=> log(log(n)) > t

as required.

Upvotes: 1

Related Questions