How to prove that $ n^b \neq O(n^a) $, if b > a > 1

50 Views Asked by At

How can we prove that $n^b \neq O(n^a) $, if b > a > 1

Based on Big-O definition:

$n^b \neq O(n^a) \iff |n^b| \le c|n^a|$

I know it's funny but I am stuck here and can't figure it out

1

There are 1 best solutions below

2
On BEST ANSWER

$$u_n = O(v_n) \iff (\exists c \in \mathbb{R}^{*})\,\, (\exists N \in \mathbb{N}) \,\, n > N \implies u_n < c \, v_n$$

And that mean if $(v_n)_{n\in\mathbb{N}}$ not null from certain range the limit $\displaystyle\lim_{n \rightarrow +\infty} \dfrac{u_n}{v_n}$ is bounded.

If $b > a > 1$ we have $\displaystyle\lim_{n \rightarrow +\infty} \dfrac{n^b}{n^a} = \lim_{n \rightarrow +\infty} n^{b-a} = +\infty$ not bounded!

Then if $b > a > 1$ : $n^b \neq O(n^a)$