How do I find the big oh of $\sqrt[k]{n}$?

Question

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?

Answer 1

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))$.

Answer 2

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$.