How do I find the big oh of $\sqrt[k]{n}$? I have a problem where $f(n)=\log n$ and $g(n)=\sqrt[k]{n}$ and I have to prove that $f(n)=O(g(n))$. I'm using the big oh formula:
$$
\begin{align}
f(n)&\leq cg(n)\\
\log n&\leq c ??
\end{align}
$$
So I need to know what the big oh of $g(n)$ is in order to go on. But how do I figure that out?
 A: One way is calculating limit:
$$\lim_{x \to \infty} \frac{\log x}{x^{\frac{1}{k}}}$$
You can use for example L'Hospital rule:
$$\lim_{x \to \infty} \frac{\log x}{x^{\frac{1}{k}}}=\lim_{x \to \infty} \frac{\frac{1}{x}}{\frac{1}{k}x^{\frac{1}{k}-1}}=\lim_{x \to \infty} \frac{k}{x^{\frac{1}{k}}}=0$$
So for $n \in \mathbb{N}$:
$$\lim_{x \to \infty} \frac{\log n}{n^{\frac{1}{k}}}$$
Now by definition of limit:
$$\exists n_0 \in \mathbb{N}  \; \forall n>n_0 \frac{\log n}{n^{\frac{1}{k}}} <1 $$
So:
$$\exists n_0 \in \mathbb{N}  \; \forall n>n_0 \log n <n^{\frac{1}{k}}$$
That means (by definition of big O) that $f(n)=O(g(n))$.
A: You need to show that for all $k$, there exists $c_k$ such that $\log n \leq c_kn^{1/k}$.
So, fix $k \in \mathbb{R}^+$
\begin{align}
\log n \leq c_kn^{1/k} &\Leftrightarrow c_k \geq \frac{\log{n}}{n^{1/k}}.
\end{align}
Let us find the maximum value of $\frac{\log n}{n^{1/k}}$. Taking the derivative, we get
\begin{equation}
\frac{d}{dx}\frac{\log n}{n^{1/k}} = \frac{n^{1/k-1} - \frac{1}{k}n^{1/k-1}\log n}{n^{2/k}}. 
\end{equation}
This equals $0$ if $n = e^k$, so letting $c_k = \frac{k}{e}$, we get a constant that is true for all $n$. 
