Consider the following pseudo code. exponentiate(int x, int n)
Consider the following pseudo code.
exponentiate(int x, int n)
{
int m=n; power= 1; z= x;
while(m>0)
{
while(m%2 ==0)
{ m= m/2; z= z*z ;
}
m=m-1; power = power*z;
}
return power;
}
What will the time complexity of function exponentiate() be?
Show answerHide answer
Correct answer: (B) Θ(log n)
Explanation
This is exponentiation by squaring: each inner step halves m, and each outer step subtracts 1 from an odd m, making it even. So m reaches 0 in about 2 log₂ n steps, giving Θ(log n).