Prove whether $f(n)$ is $O$, $o$, $\Omega$, $\omega$ or $\Theta$ of $g(n)$. $f(n) = n$, $g(n) = (\log n)^c$ for positive integer $c$.

Question

So I'm completely new to Big O notation and time complexity and here is my attempt so far. $$ \frac{f(n)}{ g(n)} = \frac{n}{ (\log n)^c} $$ and since $\log n$ grows slower than $n$, as $n$ approaches infinity the limit is also infinity.

I think this is correct, but I'm not sure how the notation works.

If you could explain how to apply big O notation to this it would be very helpful!

Thanks!

Answer 1

You showed that $\dfrac{f(n)}{g(n)}\rightarrow +\infty$ as $n\to+\infty$. Therefore : $$ \lim\limits_{n\to+\infty} \dfrac{g(n)}{f(n)} = 0$$ So that $g(n) = o(f(n))$ by definition of the o notation.