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