In big-O notation for algorithmic time-complexity analysis, given real-valued functions $f$ and $g$, $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $$ |f(x)| \leq C |g(x)| \quad \forall x > k $$
I'm struggling with the case $f(x) = x^c$ where $0 < c < 1$, and $g(x) = \log^b(x)$ where $b > 1$. Which grows faster, polylogarithmic $g(x)$ or fractional power $f(x)$?
Plotting an example suggests that polylogarithmic dominates, but how can I formally prove this?
In a formal big-O proof, you need to pick two values $k$ and $C$ and show that $0 \leq f(x) \leq C g(x)$ for every $k \geq x$.
If you're not sure how to pick you can go backwards and see how you can solve for $x$. Start with:
$$C x^c \geq \log^b(x)$$ (as the comment says a positive power of $x$ is going to grow bigger than any power of $\log x$, but even if you get it wrong here you can go back and fix it). Then do some algebraic manipulation. Since $0<c<1$ you can do $C x \geq \log^{b/c}(x)$ and here it seems like maybe taking the log of both sides might be helpful.
Then you get $\log(C x) \geq b/c \log\log(x)$. Next, move all the $x$ terms to one side and get
$\frac{\log(Cx)}{\log \log(x)} \geq \frac{b}{c}$. We think $\log x$ grows faster than $\log \log x$ but we can figure out some constants that will work for us. Since $b/c$ is a constant set before, we can just say there's some value $\ell$ for which $10^\ell/\ell \geq b/c$, and $C = 1$. I might try $x =10^{10^\ell}$ (you can try another value as well).
Then I have $$\frac{\log (10^{10^\ell})}{ \log\log(10^{10^\ell}) } = \frac{10^\ell}{\ell}.$$
At this point, you go back and write the proof saying I set $C=10$ and $k= 10^{10^\ell}$ and work through the steps backwards to show the inequality holds. As a last step, you'd have to convince yourself that $\log x$ grows faster than $\log \log x$.