Consider the following recurrenc relation:
$f(n) = f(n/2) +nlogn$
Since this does not honor the form of the Master Recurrence, we need to obtain an estimate of the asymptotic order of $f$. According to the book, we can conclude from the recurrence that:
$f(n) = \Omega(nlgn)$
How? If I'm not mistaken, for any $f(n)$ to be $\Omega(g(n))$, $f(n)$ must be greater than or equal to $Cg(n)$ (where $C$ is some constant).
How can $n$ >= $nlgn$? Much less $n$ >= $C*nlgn$? What am I missing?
What am I missing?
If $f(n) = f(n/2) +n\log n$, by definition $f(n) \ge n\log n$ if $f(n/2) \ge 0$.
Immediately $f(n) = \Omega(n\log n)$.
I believe you are mistaken: this recurrence relation can be solved via the Master Method.
The third clause in the Master Theorem (from CLR) states:
If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$, ... then $T(n) = \Theta(f(n))$.
In this case, what you are referring to as $f(n)$, $f(n/2)+n \log n$, would be $T(n)$, $f(n)$ would be $n\ \log n$, $a$ is $1$ and $b$ is $2$.
Thus, $n^{\log_b a} = n^{log_2 1 } = n^0 = 1$. To make things simple, let's let $\epsilon = 1$. Then, $n^{\log_b a + \epsilon} = n^{log_2 1 + 1} = n^{0+1} = n$. Since $n \log n = \Omega(n)$, it is the case that $T(n) = \Theta(n \log n)$. But if $T(n) = \Theta(n \log n)$, it is also the case that $T(n) = \Omega(n \log n)$.
