791 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;


edited | 791 views
0
can anyone plz explain this ques and its relevant answer?
+7
This program computes $x^n$ and T.C is $\Theta(logn)$ as n is divided by 2 each time.

answer - $x^n$
by Loyal (8.6k points)
edited by
+13
And does it with $O(\log n)$ complexity
0
question did not really ask for the complexity
+13
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
+1
Well Pointed the complexity @arjun sir that is the beauty of this question.

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.

by Boss (24k points)

1
2
3