Consider the following recursive algorithm $Trump$, which takes as input an integer $n ≥ 1$, which is a power of $\textbf{2}$:
$\textbf{Algorithm} \hspace{2mm} Trump(n):\\ \textbf{if }n = 1 \\ \textbf{then} \text{ order chicken nuggets} \\ \textbf{else if } n = 2 \\ \quad \quad \textbf{then} \text{ drink one pint of beer} \\ \quad \quad \textbf{else} \textit{ print } \thinspace ``\text{I am fabulous''}; \\ \quad \quad\hspace{2em} Trump(n/2) \\ \quad \quad \textbf{endif} \\ \textbf{endif} $
For $n$ a power of $2$, let $T(n)$ be the number of times you print $``\text{I am fabulous''}$ when running algorithm $Trump(n)$. Which of the following is true?
(a) $T(n) = \log n - 1$ for all $n \ge 2$
(b) $T(n) = \log n - 1$ for all $n \ge 1$
(c) $T(n) = \log n$ for all $n \ge 2$
(d) $T(n) = n-2$ for all $n \ge 2$
The answer is (a).
I got (c):
$T(1) = 0$
$T(2) = 0$
$T(n) \le 1 + T(n/2)$, if $n \ge 2$ $\quad(1)$
By unfolding:
Assume $n = 2^k$ for some integer $k \ge 0$
If we replace $n$ by $n/2$ in $(1)$, we get:
$T(n/2) \le 1 + T(n/2^2)$
So,
$T(n) \le 1 + T(n/2)$
$T(n) \le 1 + (1 + T(n/2^2))$
$\ldots$
$T(n) \le k + T(n/2^k)$
Substitute $2^k$ for $n$, we get:
$T(n) \le k + T(2^k/2^k)$
$T(n) \le \log n + T(1) \quad\quad 2^k \implies k = \log n$
$T(n) \le \log n + 0$
$T(n) \le \log n$, hence (c)
Where did I go wrong?
What an interesting function! Notice that $T(n) = 1 + T\left(\frac{n}{2}\right)$ for $n > 2$. More importantly, we have $T(2)=0$, so we can actually "unfold" until we hit $T(2)$, not $T(1)$. We can see that: \begin{align} T(n) &= 1 + T\left(\frac{n}{2}\right) \\ &=1 + \left(1 + T\left(\frac{n}{4}\right)\right)\\ &=1 + \left(1 + \left(1 + T\left(\frac{n}{8}\right)\right)\right)\\ & \vdots\\ &= \ell +T\left(\frac{n}{2^\ell}\right) \end{align}
for some integer $\ell$. So $$T(n) = k-1 + T\left(\frac{n}{2^{k-1}}\right) = k-1+T(2) = k-1$$ where $k = \log(n)$. Your error was in attempting to "unfold" $T(2)$, when it makes no sense to do so if $T(2) = 0$.