# Master Theorem $T(n) = 4T(n/2) + \lg n$

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

-
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

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.

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.

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

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