Master's Theorem recurrence Given recurrence relation $T(n)=8T(n/6)+n \log n$, I get that the running time of the leaves should be $n^{\log_6 8}$ and $f(n)$ should be $n \log n$, but how can I know which one is bigger ?
$n^{\log_6 8} = n^c$ for some $c&gt;1$ (you can tell that $\log_6 8 &gt; 1$ from the fact that $8&gt;6$). Then $n^c = \omega(n \log n)$.
Indeed:
$$\lim_{n \to +\infty} \frac{n^c}{n \log n} = \lim_{n \to +\infty} \frac{n^{c-1}}{\log n} = \lim_{n \to +\infty} \frac{(c-1)n^{c-2}}{1/n} = \lim_{n \to +\infty} (c-1)n^{c-1} = +\infty.$$