How can we satisfy regularity condition for $T(n) = 81T(n/9) + n^4 \log n$?

Question

Here is the question-answer

It says that regularity condition is satisfied, while regularity condition is $$81\cdot \left(\frac{n^{4}\log n}{9}\right) \leq k\cdot n^4\log n$$ where $k < 1.$

So, how is it possible that regularity condition is satisfied?

Answer 1

You are misunderstanding the regularity condition. What you wrote is not satisfied. But the correct interpretation is $$ 81 \cdot \left(\frac{n}{9}\right)^4 \log \left( \frac{n}{9} \right) = \frac{1}{81}n^4 \log(n/9) \ll k n^4 \log n, $$ which I think is pretty clear.