# Algorithm Analysis on Recurrence Relation.

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?

• This question might actually be more appropriate for the cs site. – Isaac Kleinman Nov 24 '13 at 21:27

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

• Thanks! I have a second question: Further on, the book says: Furthermore, for a sufficiently large $n: lg n \le n^\epsilon$ for any $\epsilon >0$. How does one construct that form of statement? – Chase Nov 24 '13 at 22:11
• Once you can show that $\log(n)/n \to 0$ as $n \to \infty$, it is immediate that $\log(n)/n^{\epsilon} \to 0$. – marty cohen Dec 4 '13 at 6:32

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