Using Master Theorem to prove a recurrence with f(n) = Θ(n/logn)

Question

I'm trying to use the master theorem to solve the recurrence:

$$T(n) = 4T\left(\frac{n}{5}\right) + \Theta\left(\frac{n}{\log n}\right)$$

I'm having trouble understanding how the $\Theta\left(\frac{n}{\log n}\right)$ factors into the solution, and what case to use to justify it. I've only worked with examples where $f(n)$ isn't some order notation.

is the fact that $\frac{n}{\log n}$ is not polynomial mean that this equation cannot be solved by the master theorem?

I'm confused as to what $$f(n) = \Theta\bigg(\frac{n}{\log n}\bigg)$$ means, instead of:$$f(n) = \frac{n}{\log n}$$

Answer 1

The "non-polynomial" nature of the function doesn't matter. Here, we have the parameters $$ a = 4\\ b = 5\\ f(n) = \Theta(\frac{n} {\log n}). $$

Without considering $f(n)$, the recurrence has the solution $\Theta(n^c)$ where $c= \log _b a \approx 0.861$.

Now, let me ask you: which case of the Master Theorem does this lead to? Can you compare $n^c$ with $f(n)$ and tell which grows faster?

Added Your comment is exactly right. Forget about the $\Theta(.)$ for the time being,and think only about $f(n)$ as you did.

Answer 2

The Master Theorem can indeed be applied here. As a hint, can you see why for any $\epsilon > 0$, we have that: $$ n^{1 - \epsilon} = O(\tfrac{n}{\log n}) $$