# Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$

I'm having a hard time trying to understand how to solve this recurrence relation using the Master Method:

$$T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$$

First, we have:

$$a = 10,\ b = 2$$ so we have $$n^{\log_2^{10}} = n^{\lg10}$$

Now we need to find how $$f(n)$$ compares to $$n^{\lg10}$$.

And here I'm stuck. What do I have to pay attention to in order to know whether I'm dealing with Case 1 (and look for $$O(n^{{\lg10} - \varepsilon}))$$ or Case 3 (and look for $$\Omega(n^{{\lg10} + \varepsilon}))$$ of the method?

My attempt:

From what I know $$\log(n) < n^\varepsilon\quad \forall \varepsilon > 0$$. So

$$\frac{1}{\log(n)} > \frac{1}{n^\varepsilon}$$ $$\frac{n^4}{\log(n)} > \frac{n^4}{n^\varepsilon}$$

$$\implies \frac{n^4}{\log(n)} = \Omega( n^{4-\varepsilon})$$

but I have no idea how to relate this (assuming no mistakes) with one of the two cases. In Case 1 we deal with $$O(\cdot)$$ and not $$\Omega(\cdot)$$ while in the 3rd Case the form of the exponents doesn't seem to match.

In order to apply Case 3, you have to show that $$\frac{n^4}{\log n} = \Omega(n^c)$$ for some $$c > \log_2 10$$, as well as the regularity condition (which holds for functions of the form $$n^\alpha \log^\beta n$$).
You take it from here. Hint: $$4 > \log_2 10$$.
• Is it true that $\frac{n}{\log n} = \Theta(n)$? If so, can we say that $f(n) = \Theta(n^4)$? – Jazz Feb 10 '19 at 16:20
• I graphed $\frac{n^4}{\log n}$. It looks like outgrows $n^k$ for any $k>1$. That right? Then it seems that all we need is, for sufficiently large $n$, $\Omega(n^4)$. Am I on the right track? – Jazz Feb 10 '19 at 17:49
• It is just not the case that $\frac{n^4}{\log n} = \Omega(n^4)$. Dividing both sides by $n^4$, you would get the nonsensical $\frac{1}{\log n} = \Omega(1)$. However, as you showed in the post, if $c < 4$ then $\frac{n^4}{\log n} = \Omega(n^c)$. – Yuval Filmus Feb 10 '19 at 17:51