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.

In class today, we did the following problem: $T(n)=4T(n/2) + \lg n$

So by notation in CLRS, we have $a = 4$, $b = 2$, $f(n) = \lg n$. Thus, $n^{\log_b a} = n^2$. My algorithm lecturer claimed that it doesn't fit Case 1 of the Master Theorem because "$\lg n$ is not polynomially smaller than $n^2$".

By Case 1, I mean the one described in CLRS, which is similar to the one described in the wiki page: "If $f(n) = O(n^{\log_b a - \epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$"

However, from what I can see, $\lg n = O(n^{2 - \epsilon})$ when $\epsilon = 1$. Doesn't that mean that it fits case 1 then?

So my question is:

  • If I'm wrong, what did I miss on?
  • If I'm right, what is an example that doesn't fit Case 1?

EDIT

Here's the statement of the Master Theorem copied from the book: Let $a \geq 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T(n)$ be defined on the nonnegative integers by the recurrence

$T(n) = aT(n/b) + f(n)$

where we interpret $n/b$ to mean either $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$. Then $T(n)$ has the following asymptotic bounds:

  1. If $f(n) = O(n^{log_b a - \epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{log_b a})$

  2. If $f(n) = \Theta(n^{log_b a})$, then $T(n) = \Theta(n^{log_b a} \lg n)$

  3. If $f(n) = \Omega(n^{log_b a + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leq cf(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$

share|improve this question
1  
Is the relation supposed to hold for all $n$, or just powers of $2$? –  1015 Feb 6 '13 at 18:57
    
I don't quite understand your question. Which relation are you speaking of? –  Kiet Tran Feb 6 '13 at 22:10
    
The relation in your title and at the first line of your post. –  1015 Feb 6 '13 at 22:15
    
Oh, any nonnegative $n$ is fine, I think. In the statement of the Master Theorem in CLRS, $n/b$ is interpreted to mean either the floor or ceiling of $n/b$. –  Kiet Tran Feb 6 '13 at 22:24
    
Floor or ceiling, here? –  1015 Feb 6 '13 at 22:26

2 Answers 2

up vote 0 down vote accepted

For your first question

If I'm wrong, what did I miss on?

The answer is that you didn't miss anything. $f(n)=\lg n=O(n^{2-\epsilon})$ for $\epsilon = 1$, since $\lg n=O(n)$. In CLRS terms, $\lg n$ is indeed polynomially smaller than $n^2$. In fact, any $\epsilon<2$ will work.

For your second question

If I'm right, what is an example that doesn't fit Case 1?

you might want to consider $f(n) = n^2/\lg n$. For this $f$, none of the three possible cases are satisfied, as you can verify.

While I'd be reluctant to criticize a colleague, either your lecturer was wrong or you misundertood what s/he said.

share|improve this answer
    
Since no other student (besides me and one other) pointed it out, and since I felt the statement of the theorem should be clear to anyone that regular encounter college math, believe me when I say I thought hard about how to reinterpret things, particularly about my understanding of the subject. The thing is, I did take picture of the board, and it clearly says "$f(n)$ is smaller but not polynomially; gap between case 1 & 2; can't use Master Theorem." –  Kiet Tran Feb 7 '13 at 6:02
    
@KietTran Well, then your instructor made a mistake. Not an uncommon problem in a profession where forgetfulness is institutionalized. –  Rick Decker Feb 8 '13 at 16:50

Yes, you are correct. Case 1 applies, and the solution is Theta(n^2).

Now consider $T(n) = 4T(n/2) + n^2$.

Here, case 1 does not apply because $n^2$ is not $O(n^{2-\epsilon})$ for any positive $\epsilon$. (But case 2 applies.)

share|improve this answer
    
Hope you didn't mind, but I $LaTeX$ed your answer. –  Rick Decker Feb 7 '13 at 3:04

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.