CODEWITHSUNDEEP
c++algorithmcomplexity-theory
HypNyx
HypNyx

Reputation: 35

what is the complexity of this power() function?

It is algorithm to find the power of a given number. How will the statements after the recursion affect the complexity if at all?

int power(int b, int n){
 if (n == 0)
    return 1;
 else {
    int p = power(b, n/2);
    if (n % 2 == 0) 
        return p * p;
    else 
        return b * p * p;
 }
}

Upvotes: 0

Views: 472

Answers (1)

reyad
reyad

Reputation: 1432

As, you're dividing n by 2 at each step, the algorithm runs until n reaches to 0. We can see what is happening:

n1 = n / 2
n2 = n1 / 2 = (n / 2) / 2 = n / 4 = n / (2^2)
n3 = n2 / 2 = n / 8 = n / (2^3)
...
...

It runs as long as n >= (2^x), where x is any non-negative integer.

So, we can say that, when 2^x > n, it stops(where x is the minimum possible integer, for which 2^x > n).

Now, we may write

2^k = n, // where k is a non-negative integer
or, lg(2^k) = lg(n) // here, 'lg' means 2-based log
or, k = lg(n)

So, the minimum possible value of x(for which it stops running) would be k + e, where e is a very small number, but of course, we're considering integer here(cause, no of steps). So, we could just write x = k + 1.

So, the number of steps the algorithm runs is x(considering, multiplication's complexity constant) which is equal to k + 1 or lg(n) + 1.

So, it is O(lg(n) + 1) or, we may say, O(lg(n)).

Upvotes: 3

Related Questions