Explain the following algorithm

Question

Below is the algorithm I am working with. I am to walk through the example (2,5) explaining what the algorithm does and what its worst-case runtime will be

function Do-something(a,b)
   if b = 0 then
      return 1
   else if b is even then
      x <- Do-something(a,b/2)
      return x * x
   else if b is odd then
      x <- Do-something(a,(b-1)/2)
      return x * x * a
   end if
end function

Initially looking at the function I am confused as to if it will ever output anything other than 1 or a. Here is how I see (2,5) working.

(2,5) is entered, then is sent to b being odd. x is set to so-something(2,2)

(2,2) is entered and sent to even. x is set to DO-something(2,1)

(2,1) is entered and sent to odd. x is set to do_something(2,0)

Finally (2,0) is entered and 1 is returned. Now we are sent back to the original, in which was it returned is x * x * a. Or 1 * 1 * 2.

Answer 1

It's a recursive function. Every time it calls itself, it creates a new instance of all variables. So the major mistake in your run-thru is treating all occurrences of "$x$" as the same $x$, while in fact they are all different.

Here is how it's actually going to work on the input $(2,5)$.

Instance 1. $(2,5)$ is entered. Then it's sent to $b_1=5$ being odd. $x_1$ is set to $\operatorname{DoSomething}(2,2)$, which creates a new instance of the function and its variables.

Instance 2. $(2,2)$ is entered. Then it's sent to $b_2=2$ being even. $x_2$ is set to $\operatorname{DoSomething}(2,1)$, which creates a new instance of the function and its variables.

Instance 3. $(2,1)$ is entered. Then it's sent to $b_3=1$ being odd. $x_3$ is set to $\operatorname{DoSomething}(2,0)$, which creates a new instance of the function and its variables.

Instance 4. Finally (except it isn't final yet), $(2,0)$ is entered and $1$ is returned. Returned where? That's where you made a mistake. It's returned back to $x_3=\operatorname{DoSomething}(2,0)=1$ of Instance 3.

Back to Instance 3. We're in the "$b$ is odd" case, and $x=x_3=1$. So this function returns $x\cdot x\cdot a=x_3\cdot x_3\cdot a=1\cdot1\cdot2=2$. And to where is this returned? It's returned back to $x_2=\operatorname{DoSomething}(2,1)=2$ of Instance 2.

Back to Instance 2. We're in the "$b$ is even" case, and $x=x_2=2$. So this function returns $x\cdot x=x_2\cdot x_2=2\cdot2=4$. And to where is this returned? It's returned back to $x_1=\operatorname{DoSomething}(2,2)=4$ of Instance 1.

Back to Instance 1. We're in the "$b$ is odd" case, and $x=x_1=4$. So this function returns … (you fill it in now). And since this was the original call of the function, this is the final output.

I hope this will help you see what this function actualy does.