I'm working exercises on solving recurrences, just using subsitution, master theorem is after this chapter. I'm sort of stuck on one of the exercises. It states that:

The solution of $T(n) = 2T(\lfloor n/2 \rfloor) + n$ is $O(n \lg n)$. Show that it's also $\Omega(n \lg n)$ and conclude that the solution is $\Theta(n \lg n)$.

For showing that it's $O(n \lg n)$, I've to show that $T(n) \leq cn \lg n$. This can be solved by choosing an $m < n$, like $\lfloor n/2\rfloor$, and substituting.

But if we arrive at the conclusion that $T(n) \leq cn \lg n$ for any appropriate $c > 0$ and $n \geq n_0$, than how can we say that it is also $\Omega(n \lg n)$ which implies that $T(n) \geq cn \lg n$?

Some more clarification would be nice!

  • $\begingroup$ The constants $c$ and the "sufficiently large n" $n_0$ can be different. $\endgroup$
    – mayank
    Jan 12, 2013 at 10:59
  • $\begingroup$ By that, I mean these constants for showing the upper bound can be different from these constants for the lower bound. $\endgroup$
    – mayank
    Jan 12, 2013 at 11:05
  • $\begingroup$ @mayank why don't you make this into an answer? $\endgroup$
    – Pål GD
    Jan 12, 2013 at 12:20
  • $\begingroup$ Answers of this question may be helpful. $\endgroup$
    – Raphael
    Jan 12, 2013 at 16:33

1 Answer 1


First, I would like to modify your statement slightly to remove any chance of confusion. When you say, "... $T(n) \le cn\log n$ for any appropriate $c > 0$ and $n \ge n_0$", it actually means $T(n) \le cn\log n$ for some appropriate $c > 0$ for all $n \ge n_0$.

Next, these constants for proving the lower bound can be (and generally are) different from these when proving the upper bound. I will demonstrate with your example:

Upper bound:
$T(n) = 2T(\frac{n}{2}) + n \le 2(c\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \le cn\log n - cn\log 2 + n = cn\log n - (c - 1)n$
$T(n) \le cn\log n$ for all $n$ for any $c \ge 1$
Therefore, $T(n) = O(n\log n)$

Lower bound:
I'll use a different constant $b$ for this, just to emphasize that the two constants are different.
$T(n) = 2T(\frac{n}{2}) + n \ge 2(b\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \ge bn\log n - bn\log 2 + n = bn\log n + (1 - b)n$
$T(n) \ge bn\log n$ for all $n$ for $0 \le b \le 1$
Therefore, $T(n) = \Omega(n\log n)$

So basically, you need to choose some constant such that the inequality holds for all sufficiently large $n$. These constants can (and generally are) different for different inequalities.

Note: I have assumed that $n$ is a perfect power of 2 in the above recursions to do away with the floor function. For asymptotic analysis, they do not really matter. These notes may help things become clearer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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