Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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