The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+10 votes
497 views

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;
asked in Algorithms by Veteran (59.5k points)
edited by | 497 views
0
can anyone plz explain this ques and its relevant answer?
+2
This program computes $x^n$ and T.C is $\Theta(logn)$ as n is divided by 2 each time.

2 Answers

+7 votes
Best answer
answer - $x^n$
answered by Loyal (9k points)
edited by
+7
And does it with $O(\log n)$ complexity
0
question did not really ask for the complexity
+7
yes. But that is the significance of this algorithm. Find x^n is O(log n) time is a common placement question and this algorithm is the solution.
0
fair. I just treated this as a GATE question
0
Well Pointed the complexity @arjun sir that is the beauty of this question.
+4 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.

answered by Boss (22.8k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,751 questions
46,766 answers
140,657 comments
58,519 users