Wednesday, November 26, 2014

Relationship between limit value, big-Oh, big-Omega, and big-Omicron

Sometimes a theorem is so simple that we do not think about it much. The answer to the limit between f and g says quite a bit. I found this while trying to understand it for use in the assignment:

Let f(n) and g(n) be functions such that

lim    f(n)/g(n)= A.
x -> infinity

1. If A = 0, then f(n) = O(g(n)), and f(n) <> Omicron(g(n)).
 
2. If A = 1, then f(n) = Omega(g(n)), and f(n) <> Omicron(g(n)).

3. If A is finite, but not 0, then f(n) = Omicron(g(n))

Simple but not obvious

No comments:

Post a Comment