Who can explain to me why
$$T (n) = 4T (n/2) + n/ \log n \Longrightarrow T (n) = Θ(n^2) \tag{Case 1}$$
But for
$$T (n) = 2T (n/2) + n/ \log n$$ ⇒ Master Theorem does not apply (non-polynomial difference between $f(n) = n^{\log_ba}$)
[Math] Master Theorem for solving recurrences question
recurrence-relations
Best Answer
As you can see $O(n^2)$ is at least $n$ times bigger than $O(\frac{n}{logn})$ so we can say there is a polynomial difference ( a difference measured in $n^k$).
For the second it doesn't apply because its $O(n)$ and $O(n/logn)$ the difference is not $n^k$. The difference is only $logn$ but master theorem apply only for polynomial, the difference here is not polynomial but logarithmic