Algorithms
Big-O Algorithm Computational Complexity
Big-O Domination
- O(2n) dominates O(n2)
- O(n2) dominates O(n log(n))
- O(n2) and O(n2 + n) don't dominate each other
- O(n4) dominates O(n3 + n2)
- O(log2 n) and O(log10 n) don't dominate each other
- O(3n) dominates O(2n)
- O(22n) dominates O(2n)
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: 2n dominates n2
limit n^2 / 2^n as n->infinity = 0
http://www.cs.dartmouth.edu/~dwagn/research/ordernotation.html