GATE1994-6

Question

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;

Comments

can anyone plz explain this ques and its relevant answer?

---

This program computes $x^n$ and T.C is $\Theta(logn)$ as n is divided by 2 each time.

Answer 1

answer - $x^n$

Comments

And does it with $O(\log n)$ complexity

---

question did not really ask for the complexity

---

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.

---

fair. I just treated this as a GATE question

---

Well Pointed the complexity @arjun sir that is the beauty of this question.

Answer 2

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

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

Hence ans is xⁿ.

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