CODEWITHSUNDEEP
algorithm
Blake
Blake

Reputation: 7547

Is there any difference between these two functions in regard to efficiency?

I encountered this two functions, is one more efficient than the other? what happens if I change pow1(x^2, n/2) * x to return x*pow1(x^2, n/2) in the first function?

int pow1(int x, int n){
 if(n==0)
  return 1; else
 if(n==1)
  return x; else
 if("n is odd")
  return pow1(x^2, n/2) * x ; else // change to return x*pow1(x^2, n/2) ?
 if("n is even")
  return pow1(x^2, n/2);
}

int pow2(int x, int n){
 p=1;
 for(int i=1;i<=n;i++){
  p = p*x;
 }
 return p;
}

Upvotes: 0

Views: 37

Answers (2)

Jordi Vermeulen
Jordi Vermeulen

Reputation: 1198

The second algorithm performs n multiplications. The first performs one multiplication for each bit in n; this makes it logarithmic in n. The method is called exponentiation by squaring.

what happens if I change pow1(x^2, n/2) * x to return x*pow1(x^2, n/2) in the first function? Nothing changes, as multiplication is commutative.

On a side node, is this in some programming language, or is it pseudocode? In a lot of languages, x^2 denotes a bitwise XOR between x and 2, not x squared. To square x, simply do x*x.

Upvotes: 2

Henrik
Henrik

Reputation: 23324

First is O(logn), second is O(n). So for sufficiently large n, first one is faster.

Upvotes: 1

Related Questions