Question

Consider the problem of computing the power function pow(n,x) = n^x using only multiplications. The first approach is to perform x multiplications ($n \cdot n \cdot n \cdot \ldots \cdot n$, x times). Find a better, recursive algorithm to solve this problem (by better, we mean one that uses fewer than $x$ multiplications). Write down the pseudocode for this new function, and then analyze the runtime of that recursive program by first writing out the recurrence relation $T(n, x)$ that computes the total number of multiplications required.

NOTE: SOLVE THIS USING ANY KIND OF TEXT EDITOR LIKE MICROSOFT WORD OR APPLE PAGES. PLEASE DON'T PASTE SOLUTION AS AN IMAGE.

Answer 1

Pseudo code :-
Pow(n,x) {
if(x==0)
return 1;
else if(x%2==0)
return Pow(n*n,x/2);
else
return Pow(n*n,x/2)*n;

Run time analyzation :-
  
T(n,x) = T(n*n,x/2) + O(1)
T(n,0) = 1
  
Clearly, time complexity depends only on x as the terminating condition has only x term as 0. Further, x reduces by half in each iteration(similar to binary search).

Hence, time complexity = O(log(x)).

COMMENT DOWN FOR ANY QUERY

PLEASE GIVE A THUMBS UP