Theorems.md

Theorems

May 22nd

Theorem 3.1.2 Ratio Limit Test

Let f(n), g(n) of set F. If the limit of the ratio f(n)/g(n) exists as n tends to infinity, then f and g are comparable. Moreover, assuming L = limn→􏰂f(n)/g(n) exists, then the following results hold.

• 1. 0 < L < => f(n) of Theta(g(n)), f and g have the same order
• 2. L = 0 => Oh(f(n)) for Oh(g(n)), f has a smaller order than g
• 3. L = $\inf$ => Oh(g(n)) for Oh(f(n)), f has a larger order than g