Reputation: 9
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
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