Showing bounds of a recurrence

Question

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!

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.