Using Master's Theorem with $f(n) = \lg^2 (n)$ This is a homework question about using Master's theorem, 
and I can't seem to wrap my head around this question:
$$T(n)=2T\left(\frac{n}{3}\right)+\lg^2(n)$$
I've tried to apply the Master's theorem to this question like any other Master's theorem questions: $$a=2,b=3\, \text{ and }\, f(n)=(\lg(n))^2.$$
Now, I need to figure out which case this condition falls into.
$$n^{\lg_b(a)}=n^{\lg_3(2)}=n^{0.631}$$
But the problem is that I cannot express f(n) as a polynomial for comparison as shown below:
$$n^{\lg_b(a)+\epsilon}$$
How would I figure out which case of Master's theorem this lie on?
Would taking logarithms of both sides for comparison make sense since logarithm is a monotonic function?
$$2\cdot \lg(\lg(n)) \quad\text{and} \quad (0.631+\epsilon)\cdot \lg(n)$$
Then figure out what epsilon is ...
Thank you in advance,
kpark
 A: A log-power $(\log n)^k$ is $O(n^c)$ for any $c > 0$. In other words, a power of $\log n$ grows more slowly than any positive power of $n$. (You can show this by evaluating $\lim_{n \to \infty} (\log n)^k / n^c$ using L'Hopital's rule repeatedly.) So you can assume that your additive function $f(n) = 
(\log n)^2$ satisfies $f(n) = O(n^c)$ for whatever low enough positive $c$ you need to satisfy the conditions of the Master theorem to show that the running time is the smallest possible.
A: There is a closely related recurrence that has the same complexity and can be solved exactly. This is the recurrence that has $T(0) = 0$ and $T(1) = 1$ and
$$T(n) = 2 T(\lfloor n/3\rfloor) + (1+\lfloor\log_3 n\rfloor)^2.$$
To verify that the complexity is the same note that $1+\lfloor\log_3 n\rfloor -\log_3 n \le 1$ and that $\log_3 n \in\theta(\log n).$
Now this recurrence is not difficult to solve exactly, we have that 
$$T(n) = \sum_{k=0}^{\lfloor\log_3 n\rfloor} 2^k (\lfloor\log_3 n\rfloor + 1 - k)^2.$$
This solution is particularly simple as it does not depend on the actual values of the digits in base three of $n$ but only on their number (if the added term were $n(\lfloor\log_3 n\rfloor + 1)$, for example, we would have a dependence on those digits).
Simplification yields
$$T(n) = 12 \times 2^{\lfloor\log_3 n\rfloor} 
- \lfloor\log_3 n\rfloor^2 - 6 \lfloor\log_3 n\rfloor - 11.$$
With this exact formula it is now easy to see that the asymptotically dominant term is
$$12 \times 2^{\lfloor\log_3 n\rfloor}
\in \theta\left(2^{\log_3 n}\right)
= \theta\left(3^{\log_3 2\log_3 n}\right)
= \theta\left(n^{\log_3 2}\right).$$
There is a similar but slightly more advanced calculation at this MSE link and additional material is at this other MSE link.
