Help with using Master Theorem on $T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$ I want to use the Master theorem to solve the following recurrence.
$$T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$$
We can easily see that $a=9$ and $b=3$ and $f(n) = n^2/\operatorname{lg}(n)$.
I am very new to using this theorem, and am hoping for some help or pointers at this stage.
Is there a way to eyeball which 'case' to use or should we go through each of them (that actually takes me a pretty long time).
Thanks in advance.
 A: By way of enrichment we  solve another closely related recurrence that
admits an exact solution.   Suppose we have $T(0)=0$ and $T(1)=T(2)=1$
and for $n\ge 3$
$$T(n) = 9 T(\lfloor n/3 \rfloor) + 
\frac{n^2}{\lfloor \log_3 n \rfloor}.$$
Furthermore let the base three representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k.$$
Then we  can unroll the  recurrence to obtain the  following exact
formula for $n\ge 3$
$$T(n) = 
9^{\lfloor \log_3 n \rfloor} +
\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 
9^j \frac{1}{\lfloor \log_3 n \rfloor-j} \left(
\sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j}
\right)^2
\\ = 9^{\lfloor \log_3 n \rfloor} +
\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 
\frac{1}{\lfloor \log_3 n \rfloor-j} \left(
\sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^k\right)^2.$$
Now to get an upper bound consider a string of two digits which yields
$$T(n) \le 
9^{\lfloor \log_3 n \rfloor} +
\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 
\frac{1}{\lfloor \log_3 n \rfloor-j} \left(
2 \times \sum_{k=j}^{\lfloor \log_3 n \rfloor} 3^k\right)^2
\\ = 
9^{\lfloor \log_3 n \rfloor} +
\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 
\frac{1}{\lfloor \log_3 n \rfloor-j} \left(
3^{\lfloor \log_3 n \rfloor+1} - 3^j\right)^2
\\ = 9^{\lfloor \log_3 n \rfloor} +
9\times 3^{2\lfloor \log_3 n \rfloor}
\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 
\frac{1}{\lfloor \log_3 n \rfloor-j} 
\left(1 - 3^{j-(\lfloor \log_3 n \rfloor+1)}\right)^2
\\ = 9^{\lfloor \log_3 n \rfloor} +
9\times 3^{2\lfloor \log_3 n \rfloor}
\sum_{j=1}^{\lfloor \log_3 n \rfloor} 
\frac{1}{j} 
\left(1 - 3^{-j-1}\right)^2
\\ = 9^{\lfloor \log_3 n \rfloor} +
9\times 3^{2\lfloor \log_3 n \rfloor}
\sum_{j=1}^{\lfloor \log_3 n \rfloor} 
\frac{1}{j}\left(
1 - \frac{2}{3} 3^{-j} + \frac{1}{9} 3^{-2j}\right).$$
Note  that  this bound  is  attained and  cannot  be  improved. It  is
asymptotic to
$$9^{\lfloor \log_3 n \rfloor} +
9\times 3^{2\lfloor \log_3 n \rfloor}
\left(H_{\lfloor \log_3 n \rfloor} +
\frac{2}{3}\log(2/3) -\frac{1}{9} \log(8/9)\right)
\\ = 9^{\lfloor \log_3 n \rfloor} +
9\times 3^{2\lfloor \log_3 n \rfloor}
\left(H_{\lfloor \log_3 n \rfloor} + 
\frac{1}{3}\log 2 - \frac{4}{9}\log 3\right).$$
The lower bound is for the case of a one digit followed by a string of
zeros and yields
$$T(n) \ge 
9^{\lfloor \log_3 n \rfloor} +
\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 
\frac{1}{\lfloor \log_3 n \rfloor-j} \left(
3^{\lfloor \log_3 n \rfloor}\right)^2
\\ = 9^{\lfloor \log_3 n \rfloor} +
3^{2\lfloor \log_3 n \rfloor}
\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} 
\frac{1}{\lfloor \log_3 n \rfloor-j}
= 9^{\lfloor \log_3 n \rfloor} +
3^{2\lfloor \log_3 n \rfloor}
H_{\lfloor \log_3 n \rfloor}.$$
The lower bound too is attained.

Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$\color{#0A0}{3^{2\lfloor \log_3 n \rfloor} H_{\lfloor \log_3 n \rfloor}
\in \Theta\left(\log\log_3(n) \times  3^{2 \log_3 n}\right) 
= \Theta\left(\log\log n \times n^2\right)}.$$
These are in agreement with what the Master theorem would produce.

Addendum. Wikipedia lists the above as an inadmissible case for the Master Theorem. However Akra-Bazzi applies and the reader is invited to do this calculation.
