How does lim n → ∞ f ( n ) g ( n ) = 0 imply that f ( n ) ∈ O ( g ( n ) ) ?

Question

How does       lim          n      →      ∞                  f      (      n      )              g      (      n      )        =  0 imply that   f  (  n  )  ∈      O    (  g  (  n  )  ) ?

Kobe Ortiz · Accepted Answer

By definition,   f  (  x  )  ∈      O    (  g  (  x  )  ) if and only if there exists some   N  &amp;gt;  0 such that      |    f  (  x  )      |    ≤  N      |    g  (  x  )      |  for all x greater than some       x    0  . Given the above limit, for any   ϵ  &amp;gt;  0 we have      |                  f        (        x        )                    g        (        x        )              |    &amp;lt;  ϵfor x greater than some       x    0  . If we take   N  =  ϵ then we have the required N for      |    f  (  x  )      |    ≤  N      |    g  (  x  )      |  so this shows that   f  (  x  )  ∈      O    (  g  (  x  )  ). In fact, we have   f  (  x  )  ∈      o    (  g  (  x  )  ) since the above holds for every   N  &amp;gt;  0.

How does lim_(n => infty)(f(n))/(g(n))=0 imply that f(n) in O(g(n))?

Open question

Answer & Explanation

New Questions in Differential Calculus