Reccurrence equation and finding suitable algorithm

Question

I'm given the following recurrence equation:

$$\begin{align*} T(1) &= 0\\ T(n) &= T(n/2) + 1 && \text{when $n > 1$ is even}\\ T(n) &= T((n+1)/2) + 1 && \text{when $n > 1$ is odd.} \end{align*}$$

The problems I have are the following:

1) What does $T(1) = 0$ mean when it comes to writing computer program? It cannot be

return some_constant;

because this gives the complexity of $T(1) = 1$. Am I right?

2) I'm supposed to find an algorithm whose time complexity can be described using the given equation. I was thinking of Fast Power algorithm, because it has the same $O(n) = \log(n)$, but it's described differently:

$$\begin{align*} T(1) &= 1\\ T(n) &= T(n/2) + 1 &&\text{when $n > 1$ is even}\\ T(n) &= T((n-1)/2) + 1 &&\text{when $n > 1$ is odd.} \end{align*}$$

Answer 1

1) It doesn't mean anything, for two reasons:

• First of all, it's important to distinguish between an algorithm vs the running time of an algorithm. $T(\cdot)$ is not an algorithm; it's a function. For instance, $T(n)$ might be the running time of a computer program, as a function of the size of its input, but it's not the program itself. Anyway, $T(n)$ is just a mathematical function: if it is intended to represent the running time of some algorithm, that should be stated explicitly.

• Second, every algorithm needs to take at least at least one step, so the running time always has to be at least one: it can never be zero. Therefore, it doesn't make sense to have a running time of zero. This might be a bit of a quibble/nitpick.

2) I suggest you do a bit more practice with the reverse: given a simple algorithm, work out a recurrence relation for its running time. Once you feel like you're able to do that confidently, you'll probably find this exercise easy.

See also our reference question, How to come up with the runtime of algorithms?. There's also a more advanced, sophisticated treatment at Is there a system behind the magic of algorithm analysis?.