stuck with master method $$T (n) = 3T (n/5) + \log^2 n$$
i am trying to solve this recurrence i have been told that it is master methods case 1 but how do i compare $\log^2n$ with $n^ {\log_5 3}$
 A: A rule of thumb is that polynomial functions always grow faster than logarithmic functions.  E.g. this lecture. So your polynomial function asymptotically dominates your log function, giving you case 1.
If you want to know why powers grow faster than logs, you can put the functions in a ratio and then evaluate $\lim_{n\to \infty}  \frac{f(n)}{g(n)}$.
A: This comment below makes explicit what the first answer already said, and hopefully removes the confusion regarding polylogs that seems to persist in the OP's mind.
To see why, consider $$\lim_{n \to \infty} \frac{(\log n)^k}{n^\epsilon}$$ for any positive $\epsilon$ and any positive integer $k$ (integrality is not really necessary, but suffices for our purposes).
We have
$$\lim_{n \to \infty} \frac{(\log n)^k}{n^\epsilon} = \lim_{n \to \infty} \underbrace{\frac{\log n}{n^{\epsilon/k}}\cdots \frac{\log n}{n^{\epsilon/k}}}_{k-\mathrm{times}}.$$
Thus, it all boils down to proving that $$\lim_{n \to \infty} \frac{\log n}{n^\gamma} = 0,$$
where $\gamma > 0$, and we already know how to prove this. 
So, I hope this provides the clarification the OP sought.
A: So we want to show that $T(n) = \Theta(n^{\log_{b}a})$ and $f(n) = O(n^{\log_{b}(a)-\epsilon})$. So $a=3, b=5, f(n) = \log^{2} n$, and $\log_{5} 3 = 0.6826$. So we check the following:


*

*$f(n) = \log^{2} n = O(n^{0.6826- \epsilon})$. So choose any $\epsilon >0$. In other words, $\log^{2} n \in o(n^{0.6826- \epsilon})$. Note the derivative of $(\log n)^2 = \frac{2 \log n}{n}$ and the derivative of $n^{0.6826}$ is $\frac{0.6826}{n^{0.3174}}$. 


The result follows. 
A: There  is another  closely  related recurrence  that  admits an  exact
solution. Suppose we have $T(0)=0$ and $T(1)=T(2)=T(3)=T(4)=1$ and for
$n\ge 5$
$$T(n) = 3 T(\lfloor n/5 \rfloor) + \lfloor \log_5 n \rfloor^2.$$
Then we  can unroll the  recurrence to obtain the  following exact
formula for $n\ge 5$
$$T(n) = 3^{\lfloor \log_5 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_5 n \rfloor -1} 
3^j \times (\lfloor \log_5 n \rfloor - j)^2.$$
Note that this is independent of the actual digits of $n.$
This simplifies to
$$\frac{5}{2} 3^{\lfloor \log_5 n \rfloor}
- \frac{1}{2} \lfloor \log_5 n \rfloor^2
- \frac{3}{2} \lfloor \log_5 n \rfloor
- \frac{3}{2}.$$
Now the  first term is  obviously the dominant one  asymptotically, so
that we get the following answer for the complexity of the recurrence:
$$T(n)\in\Theta\left(3^{\lfloor \log_5 n \rfloor}\right)
= \Theta\left(3^{\log_5 n}\right)
= \Theta\left(5^{\log_5 3 \times \log_5 n}\right)
= \Theta\left(n^{\log_5 3}\right).$$
This agrees with what the Master Theorem would say.
This MSE link has a series of similar calculations.
