Algorithms

• O(2ⁿ) dominates O(n²)
• O(n²) dominates O(n log(n))
• O(n²) and O(n² + n) don't dominate each other
• O(n⁴) dominates O(n³ + n²)
• O(log₂ n) and O(log₁₀ n) don't dominate each other
• O(3ⁿ) dominates O(2ⁿ)
• O(2²ⁿ) dominates O(2ⁿ)

limit dominated/dominating as n->infinity = 0

If the Big-O complexity of an algorithm dominates another then the limit of the dominated algorithm divided by the dominating algorithm will approach zero as n approaches infinity.

Example: 2ⁿ dominates n²

limit n^2 / 2^n as n->infinity = 0

http://www.cs.dartmouth.edu/~dwagn/research/ordernotation.html

http://bigocheatsheet.com