# Solving recurrences with the Substitution Method

I have several problems like this to do, but I am having a hard time understanding how they get from one step to the next in the example (see note in picture). If I can understand this example I think I'll be good. Also want to point out that this is just an example, not the actual homework problem.

-

To give a direct answer to your question it comes from the guess in step $(a)$.

$T(n) = n \log_2 (n) + n$ is the guess you made in step $(a)$. Using that replace $n = \frac{n}{2}$, $T(\frac{n}{2}) = \frac{n}{2} \log_2 (\frac{n}{2}) + \frac{n}{2}$.

$T(\frac{n}{2}) = \frac{n}{2} (\log_2 (n) - \log_2(2)) + \frac{n}{2} = \frac{n}{2} \log_2 (n) - \frac{n}{2} + \frac{n}{2} = \frac{n}{2} \log_2 (n)$

Hence, $T(n) = 2 T(\frac{n}{2}) + n = 2 \frac{n}{2} \log_2 (n) + n = n \log_2 (n) + n$

While solving some recurrences it is good to recognize some nice things about the recurrence you are actually solving. For instance in this recurrence, notice that at each step you are dividing $n$ by $2$. So strictly speaking through the recurrence you can only obtain $T(2^m)$ where $m \in \mathbb{N}$. For instance, $T(3)$ cannot be obtained using this recurrence. However, such recurrences come up when you do certain things, when $n$ is really large, recursively using say a binary tree. When $n$ is really large you are interested mainly in how the solution behaves in an asymptotic sense and not the precise expression for the solution. In such cases, you assume that $n=2^m$ for the simplicity of calculations and the cost for all $n$ (even when $n$ is not a power of $2$) can be shown to obey the solution, obtained by the assuming $n=2^m$, in an asymptotic sense.

If you were to rewrite the recurrence in terms of $m$, and call $T(2^m) = S(m)$, then we would get

$S(m) = 2 S(m-1) + 2^m$ since $\frac{n}{2} = 2^{m-1}$.

$S(m-1) = 2 S(m-2) + 2^{m-1}$.

$S(m) = 4 S(m-2) + 2^m + 2^m$ and so on (hidden induction here) to get

$S(m) = 2^m S(0) + 2^m + 2^m + \cdots + 2^m + 2^m = m 2^m + 2^m$.

Hence $T(n) = n \log_2(n) + n$ since $n = 2^m$ i.e. $m = \log_2(n)$

-
I get it, I am so retarded. I wasn't seeing that what I have circled in blue was actually my guess with n/2 substituted for n. I just needed to read it a different way, thanks a lot. – ubiquibacon Jan 31 '11 at 5:07

As they say, it is a guess. If (as in a) $T(n)=n lg n + n$ you just substitute to get the one you ask "To here". So the real question is whether induction is justified. The point is that if the expression for T is valid up to n it is valid up to 2n (and you need to explain in this case what happens for odd $n$) then it is valid for all $n$.

-