## Microsoft Interview Question

Applications Developers**Country:**India

**Interview Type:**In-Person

@Ryan: Slight modification in your code and now it will run in O(logN) time....

see the changed code below

```
public static int Power(int base, int expo){
if(expo == 0) return 1;
if(expo == 1)
return base;
if(expo%2==0)
return (Power(base*base,expo/2);
else
return base*Power(base*base,(expo-1)/2);
}
```

@Ashupriya you mean O(n log n) right?

T(n) <= T(n/2) + O(1)

O(1) work to multiply the results from the recursive calls.

No I mean O(logN) and not O(NlogN)

if you see the logic carefully, we are doing less than n recurssive calls, each step tries to calculate 2 powers,

Moreover Recursion is generally not O(N Log N)....

I am a bit confused about the complexity.

We will be still doing 'exponent' number of product operations.

Since the multiplication is the costliest operation here, won't the complexity still be O(n) (Assuming a sequential execution algorithm) even though the loops/recursions run till O(log n)?

In that case why not just use a simple for loop with a product variable holding the final result?

I do not really prefer to solve this using recursion. This version will be better I think.

```
#include<iostream>
int power(int x, int n)
{
if (n < 0)
return 1 / power(x, -n);
int res = 1;
int base = x;
while (n > 0)
{
if (n & 1 == 1)
res *= base;
base *= base;
n >>= 1;
}
return res;
};
int main()
{
int res = power(3, 3);
return 0;
}
```

Base cases:

if p = 0, then return 1

if p = 1, then return base

0^p = 0

1^p=1

2^p = 2<<(p-1), p>=2

If Base % 2 == 0 then

(2*n)^p => 2^p * n^p => O(logp)

Else if Base % 2 > 0 then

B^p = B * B^(p-1) O(p)

Overall running time: O(p*logp)

- Ryan August 25, 2012