Finding Big Theta of Recurrence Relation $8T(n/3)+n^2/\log_3(n)$

Question

Getting stuck on finding the geometric series after finding the sum for this recurrence. I didn't think master theorem applied to this because I thought n^2/log3(n) was not a polynomial but I could be wrong.

Answer 1

Welcome to MSE!

The master theorem is applicable here. In particular:

We see $c_{\text{crit}} = \log_3(8) \approx 1.89$, so we want to compare the term $n^2 / \log_3(n)$ with $n^{1.89}$ (roughly).

Of course, $n^2 / \log_3(n) = \Omega(n^{1.89})$ since

$$ \lim_{n \to \infty} \frac{n^2 / \log_3(n)}{n^{1.89}} = \lim_{n \to \infty} \frac{n^{.11}}{\log_3(n)} = \infty > 0 $$

So we fall into case $3$ of the master theorem (at least as listed on wikipedia).

Our last check is to show the "regularity condition" holds. That is,

$$8f(n/3) \leq k f(n)$$

for some $0 < k < 1$ and $n$ large.

Thankfully, we expand this to

$$ 8 \frac{(n/3)^2}{\log_3(n/3)} \leq k \frac{n^2}{\log_3(n)} $$

Which happens if and only if

$$ \frac{8}{9} \frac{\log_3(n)}{\log_3(n) - 1} \leq k $$

But since $\frac{\log_3(n)}{\log_3(n) - 1}$ limits to $1$, if we choose $8/9 < k < 1$, the desired inequality will hold for large $n$.

This lets us conclude

$$T(n) = \Theta(n^2/\log(n))$$

---

I hope this helps ^_^