How does this recurrence relation fit the algorithm?

Question

I have the following pseudo code:

Multiply(y,z)    
1. if (z==0) return 0     
2. else if (z is odd)    
3.    then return (Multiply(2y, floor(z/2)) + y )    
4. else return (Multiply(2y, floor(z/2)))    

Towards analysing this procedure's runtime, this recurrence relation is given as answer:

$\qquad \displaystyle T(z) = \begin{cases} 0 & z=0 \\ T(z/2)+1 & z>0\end{cases}$

Why is $T(z)=0$ when $z=0$? Shouldn't it be $1$ for this case?

And, the $+1$ in $T(z/2)\mathbf{+1}$ is because the worst case is (multiply(2y, floor(z/2)) + y (note the + y). Am I correct?

Answer 1

You should be careful about what is being counted. If you want to count "runtime" (as in, number of statements) the given recurrence is clearly wrong.

Reverse-engineering from the recurrence, it is probably supposed to count additions. In particular, note how the computation the parameters for recursive calls is ignored. I hope it is clear that the recurrence is correct for the worst-case then; your reasoning for $+1$ is spot-on.

Why does restricting your self to additions make sense here? Additions are one of the statements that are executed most often (in the worst case, that is ignoring line 4.). That means that the true runtime (in a theoretic model) is proportional to the number of additions. Since you are (most likely) after asymptotics in terms of $O$, counting additions is sufficient: the proportion-constant is lost in $O$, anyway.

You can, for the fun of it, set up a recurrence counting all statements. You'll see that the result has the same asymptotic growth as the one you were given.

Answer 2

There's a bit of ambiguity in what you're looking for here. I am going to assume it's the running time of the function.

I agree that it should be 1 when $z=0$ because it generally is considered to take $O(1)$ operations to return a function value. However, this will only affect your final answer by an additive constant of 1.

The $+1$ factor in the recurrence $T(z) = T(z/2) + 1$ is caused by the overhead of calling the subfunction.

In other words, what happens at a given value of $z$ is:

The function is called (generally $O(1)$ work just to set up the stack, etc.)

The program tests whether $z$ is odd ($O(1)$ work)

The function calls itself with a smaller instance ($T(z/2)$ work), and then does an addition before returning ($O(1)$ work).

Add these up, and you get $T(z) = T(z/2) + O(1)$. You can substitute $1$ instead of $O(1)$ in this case and you'll get the same answer so long as you're only worried about asymptotics.