1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is it true that $\frac{n}{\log n} = \Theta(n)$? If so, can we say that $f(n) = \Theta(n^4)$? $\endgroup$ – Jazz Feb 10 at 16:20
  • $\begingroup$ No, that's actually false. You'll need to do something more subtle. Spend a few hours on it. It's the only way to learn and get better. $\endgroup$ – Yuval Filmus Feb 10 at 16:20
  • $\begingroup$ 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? $\endgroup$ – Jazz Feb 10 at 17:49
  • $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Feb 10 at 17:51

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.