If we have arbitrary constants $x > 1$ and $y > 0$, how can I go about proving that $x^n$ is not $O(n^y)$?
I think this may be achievable using recurrences but I am not sure about the methodology behind that, so any help is appreciated.
Asked
Active
Viewed 203 times
3
-
1Can you compute $\lim_{n \to \infty} x^n/n^y$? – Antonio Vargas Mar 23 '18 at 23:18
-
@AntonioVargas I assume it is infinity as an exponential grows faster than a polynomial is the standard situation I have been taught, I was wondering if there was anything more to say about this particular case though – Harrison W. Mar 24 '18 at 12:20
-
1Rather than assuming, you can use L'Hopital's rule to prove it. Once you've done that, do you see how it solves your problem? – Antonio Vargas Mar 24 '18 at 19:45
-
@AntonioVargas ah I forgot about l’hopitals, then yes as by definition the ratio tending to infinity implies the top grows faster than bottom, thank you – Harrison W. Mar 24 '18 at 19:46
-
1Glad to help! If you post your solution below, I'll be happy to upvote it. – Antonio Vargas Mar 24 '18 at 19:48
-
@AntonioVargas is my answer satisfactory do you think? – Harrison W. Mar 24 '18 at 20:01
1 Answers
1
We can compute the limit of the ratio of the two functions by applying L'Hopital's rule $\lceil y \rceil$ times:
$$\lim_{n\to\infty} \frac{x^n}{n^y} = \lim_{n\to\infty}\frac{x^n\log^y x}{y!}= \infty$$
This is clear as $y$ is a defined constant and thus the bottom half of the fraction is inconsequential as $n\to\infty$.
Now, for $x^n$ to be $O(n^y)$ we require $\exists c$ such that $x^n \le c \cdot n^y \implies \frac{x^n}{n^y} \le c$ beyond some $n_0$. As $n \to \infty$ we have calculated the ratio which leads to a contradiction as no $c$ can exist which is $\ge \infty$ beyond $n_0$. As such, $x^n$ is not $O(n^y)$.
Harrison W.
- 777
-
I think you mean that you need to apply L'Hopital's rule $\lceil y \rceil$ times. (Prove this. What does the ratio look like after doing it?) – Antonio Vargas Mar 24 '18 at 20:33
-
@AntonioVargas Ah ok, so applying it $y$ times would lead to $\lim \frac{x^n \cdot \log^y x}{y!}$ where $y$ is a constant, meaning clearly that the limit must be infinity? – Harrison W. Mar 24 '18 at 20:38
-
If $y$ is an integer, yes. If $y$ is something like $3/2$, the result will look a bit different. – Antonio Vargas Mar 24 '18 at 20:50
-
Ok cool, I will try to work in the more general case too for the ceiling, I really appreciate the help – Harrison W. Mar 24 '18 at 21:14