Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

enter image description here

share|cite|improve this question
up vote 6 down vote accepted

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)$

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.