Question discussion

Consider the following pseudo code.What will the time complexity of function exponentiate() be?

359046Medium DSSSB TGT Computer Science 0 replies 0 views
0
Consider the following pseudo code.
What will the time complexity of function exponentiate() be?
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;
}
  • AOption A
  • BOption B
  • COption C
  • DOption D
Correct answer: B

Explanation

The inner loop halves m each time and the outer loop reduces m by 1 only when m is odd, so the number of steps is proportional to the number of bits of n. The time complexity is Θ(log n).

Discussion 0

Nobody has replied yet. Start the discussion!