I have a recurrence as follows:
\begin{equation}
T(n) = \begin{cases}a, & \text{for $n=1$}\\
T(\dfrac{n}{2})+b,&\text{for $n\geq2$}
\end{cases}
\end{equation}
$a$ and $b$ are some undefined constant.
I'm asked to find an explicit formula using substitution, showing my work for $k$ iterations. I understand, conceptually, how to substitute:
\begin{align*}
T(n) &= T(n/2)+b\\
T(n/2) &= T(n/4) + 2b\\
T(n/4) &= T(n/8) + 3b\\
T(n/8) &= T(n/16) + 4b
\end{align*}
WolframAlpha tells me that this recurrence resolves to $T(n) = a + \dfrac{b \log(n)}{\log(2)}$, but I have no idea how it arrived there, or if that is even correct.
What is the correct way to perform this substitution to arrive at an explicit formula?
Best Answer
First, one can notice that this recurrence is defined only for numbers $n$ which are powers of 2.
To solve the recurrence, you can try to unravel it.
Namely, $$T(n) = b+T\left(\frac{n}{2}\right) = b+b+T\left(\frac{n}{4}\right)= b+b+b+T\left(\frac{n}{8}\right) = 3b+T\left(\frac{n}{2^3}\right)$$
We can see that the coefficient next to $b$ increases by one in every step and that the argument of $T$ gets divided by two every time. So, we can infer that the general formula would be: $$T(n) = k\cdot b + T\left(\frac{n}{2^k}\right)$$ for some $k\in\mathbb N$.
But, we are aiming to get $n=2^k$, in order for the chain to terminate. This gives us that $k=\log_2 n$.
Now we have $$T(n) = b\log_2 n + T(1) = b\log_2 n+a$$
You can use mathematical induction to prove that this is indeed the general formula for $T(n)$.
Also, this formula is equivalent to the formula WolframAlpha gave.