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?


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

  • 1
    $\begingroup$ Is the relation supposed to hold for all $n$, or just powers of $2$? $\endgroup$
    – Julien
    Feb 6 '13 at 18:57
  • $\begingroup$ I don't quite understand your question. Which relation are you speaking of? $\endgroup$
    – Kiet Tran
    Feb 6 '13 at 22:10
  • $\begingroup$ The relation in your title and at the first line of your post. $\endgroup$
    – Julien
    Feb 6 '13 at 22:15
  • $\begingroup$ 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$. $\endgroup$
    – Kiet Tran
    Feb 6 '13 at 22:24
  • $\begingroup$ Floor or ceiling, here? $\endgroup$
    – Julien
    Feb 6 '13 at 22:26

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

  • $\begingroup$ Hope you didn't mind, but I $LaTeX$ed your answer. $\endgroup$ Feb 7 '13 at 3:04

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.

  • $\begingroup$ 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." $\endgroup$
    – Kiet Tran
    Feb 7 '13 at 6:02
  • $\begingroup$ @KietTran Well, then your instructor made a mistake. Not an uncommon problem in a profession where forgetfulness is institutionalized. $\endgroup$ Feb 8 '13 at 16:50

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.