# Reccurrence equation and finding suitable algorithm

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*}

• It seems like they made a mistake. – Yuval Filmus Jan 6 '16 at 22:07

• 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.