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?

  • $\begingroup$ This question might actually be more appropriate for the cs site. $\endgroup$ – 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)$.

  • $\begingroup$ 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? $\endgroup$ – Chase Nov 24 '13 at 22:11
  • $\begingroup$ Once you can show that $\log(n)/n \to 0$ as $n \to \infty$, it is immediate that $\log(n)/n^{\epsilon} \to 0$. $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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