0

For all real numbers, if $x \leqslant y, n^x \in \mathcal O(n^y)$.

This is a homework question, so I'm just looking for a little guidance with this question, and not the answer. I understand how to prove Big O questions using actual functions, but this is something new so I'm unsure. I know that I have to find a c and b that make this true, but I can't figure out how to do the algebra to arrive at that conclusion. Any hints with this?

So far, I've only got the first step:

$n^x \le c*(n^y)$

Where can I go from here?

Guy
  • 8,857
  • 1
  • 28
  • 57
user134796
  • 23

1 Answers1

1

You may find the limit test helpful here. Let $L = \lim_{n \to \infty} \frac{f(n)}{g(n)}$. $f(n) \in O(g(n))$ if $L < \infty$. If $0 < L < \infty$, then $f(n) \in \Theta(g(n))$, which implies $f(n) \in O(g(n))$. Otherwise, if $L = 0$, then $f(n) \in o(g(n))$, which implies that $f(n) \in O(g(n))$.

ml0105
  • 14,674
  • How can I calculate the limit with f(n) = n^x and g(n) = n^y? Just choose any arbitrary values that satisfy x<=y? – user134796 Mar 26 '14 at 17:59
  • 1
    It is not true that $f \in O(g)$ if and only if $L < \infty$; the limit may not exist. If you had defined $L = \limsup_{n \to \infty} |f(n)/g(n)|$ then it would be true. – Antonio Vargas Mar 26 '14 at 18:13
  • User134796- Think about applying L'Hosptial's rule. Note that since $x \leq y$, the limit will be at most $1$. If $x < y$, the limit will be $0$.

    Antonio Vargas- Thanks for the catch. I've edited out the biconditional.

     – ml0105 Mar 26 '14 at 18:42