recategorized by
2,694 views
19 votes
19 votes

What function of $x$, $n$ is computed by this program?

Function what(x, n:integer): integer:
Var
    value : integer
begin
    value := 1
    if n > 0 then
    begin
        if n mod 2 =1 then
            value := value * x;
        value := value * what(x*x, n div 2);
    end;
    what := value;
end;
recategorized by

3 Answers

Best answer
5 votes
5 votes

How you will compute $x^{n}$?

The first solution that we may think of is a brute force approach which is multiplying x, n times. Time complexity of this solution is $\Theta (n)$.

int fun(n) 
{ 
    int ans=1;  
    for(int i=1;i<=n;i++) 
        ans=ans*x; 
    return ans;
}

Can we do better? Can you reduce the time complexity of this problem?

The answer is yes and the solution is given in question 6.

This method is known as Exponentiation_by_squaring or Binary_exponentiation.

Algorithm: Exponentiation by squaring - Wikipedia | Binary Exponentiation - Competitive Programming Algorithms (cp-algorithms.com)

The time complexity of this solution is $O(\log n).$ That is the significance of this algorithm.

selected by
15 votes
15 votes
answer - $x^n$
edited by
8 votes
8 votes

take what(2,8) U will get 256 as ans.

what(2,7) U will get 128 as ans.

Hence ans is xn.

But the beauty of this code is it is done in O(logn) time instead of O(n) time.

Related questions