I have two functions:
$f(n) = n^a$ with $a \in N$ and $a > 1$
$g(n) = 2^{\sqrt{ln(n)}}$.
I'm asked to see whenever or not $O(f(n)) \in O(g(n))$ or vice versa or if equal to each other.
To do this we can use the limit rule which states that If you have :
$\lim _{n\rightarrow \infty }\dfrac {f\left( n\right) }{g\left( n\right) }=0$ then it means that $O(f(n)) \in O(g(n))$.
$\lim _{n\rightarrow \infty }\dfrac {f\left( n\right) }{g\left( n\right) }=+\infty$ then it means that $O(g(n)) \in O(f(n))$
$\lim _{n\rightarrow \infty }\dfrac {f\left( n\right) }{g\left( n\right) }=c$ and $c \in(0, +\infty)$ then it means that $O(g(n)) = O(f(n))$, $\Theta (f(n)) = \Theta (g(n))$
Considering the above I try to do:
$\lim _{n\rightarrow \infty }\dfrac {n^a}{2^{\sqrt{ln(n)}}}$
- It seems obvious that $n^a$ is trending towards $\infty$ because $a>1$.
- It seems also obvious that $ln(n)$ is trending towards $\infty$ aswell which implies that we have $2^\infty$. However I'm not so sure about $2^\infty$ trending towards $\infty$ it resembles $1^\infty$ which is a known case of indetermination.
- If we assume that $\dfrac{1}{2^\infty} = \dfrac{1}{\infty}$ then what happens to the overall function $\dfrac {n^a}{2^{\sqrt{ln(n)}}}$.
- Using the Hospital rule doesn't seem to be the right choice because it seems to give complicated derivatives.
How do I go about solving this?
What you can do is take the natural log of the limit, evaluate and then exponentiate your answer to get the limit. See this post: Evaluating limit using logarithms.