Say we have a recurrence equation as
$$
T(n) =
\begin{cases}
T\left(\frac n2\right) +n & \text{if }n\ge2 \\
1 & \text{if }n=1
\end{cases}
$$
Would the first substitution be like this?
$$\left(T\left(\frac n4\right) + \frac n2\right) + n$$
A little confused with these. If you could show the first 3 or so steps, or any other help would be greatly appreciated 🙂
Best Answer
Let $n = 2^k$.
$$\begin{align}T\left(n\right) & = T\left(\frac n2\right) + n \\ &= \left[T\left(\frac n4\right) + \frac n2\right] + n\\ & = \left[T\left(\frac n8\right) + \frac n4\right] + \frac n2 + n\\ & = \dots\\ & = T\left(\frac n{2^k}\right) + \left[n + \frac n2 + \frac n4 + \cdots + \frac{n}{2^{k-1}}\right]\\ & = 2n - 1\end{align}$$