CODEWITHSUNDEEP
javarecursion
Linda
Linda

Reputation: 251

Analyse of power recursive function

I want to write power recursive function that it's analyse is o(n): This is my idea is it true?? Or if the analyse of this code is not o(n) can anyone help me to change it to make it better?? thanks in advance

  power(int x , int n)
  {
      if(n==0)
        return 1;
      else
        return x*power(x,n-1);
  }

Upvotes: 1

Views: 547

Answers (5)

Arash Saidi
Arash Saidi

Reputation: 2238

This is O(n) time because you are counting down from the input n to where n is 0.

Upvotes: 1

Fabio Carello
Fabio Carello

Reputation: 1102

You are calling "k" times your function and its upper bound matches with its lower bound. So i think it's Theta(k)

Upvotes: 1

Ankit Rustagi
Ankit Rustagi

Reputation: 5637

You are calling your function recursively "k+1" times. Example for power(10,3), you make the following function calls

power(10,3)  -
power(10,2)   |  k+1 times
power(10,1)   |
power(10,0)  -

Thus the complexity is O(k) and not O(n) !

Upvotes: 1

rgettman
rgettman

Reputation: 178253

This method is O(k), not O(n), because it will perform k recursive calls. Additionally, the base case k being 0 should return 1, not n.

Upvotes: 1

Luiggi Mendoza
Luiggi Mendoza

Reputation: 85779

There are two problems:

  1. Power of N to 0 is 1. This must be constant O(1).
  2. Power of N to 1 is N. This also must be constant O(1).

After that, the code should work. It will behave in linear time for the power, so it will be O(k).

Upvotes: 1

Related Questions