Big-O notation with properties

Big-O notation: f(n) = O(g(n)) if there are positive constants c and n₀ with f(n) ≤ c·g(n) for all n ≥ n₀. It gives an upper bound on the growth rate. Example: 2n + 10 ≤ 3n for n ≥ 10, so 2n + 10 = O(n).

Properties

1. Reflexivity: f(n) = O(f(n)).
2. Transitivity: if f = O(g) and g = O(h), then f = O(h).
3. Constant factor: O(c·f(n)) = O(f(n)) for c > 0.
4. Sum rule: if f₁ = O(g₁) and f₂ = O(g₂), then f₁ + f₂ = O(max(g₁, g₂)).
5. Product rule: f₁ · f₂ = O(g₁ · g₂).
6. Polynomial: if f(n) = aₖnᵏ + ... + a₁n + a₀, then f(n) = O(nᵏ).
7. If f(n) ≤ g(n) for all large n, then O(f) ⊆ O(g).
8. Growth order: O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(2ⁿ).