Question about the asymptotic growth rate of two functions

Question

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.

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