Big Oh Rules

Notation

For notation not displayed here, check out the notation page.

O = Big Oh = f(x) is in the "Big Oh" for g(x) if f(x) is equal or slower growing then g(x).

These are the rules for dealing with Big Oh Notation

1) Coefficient Rule
f(n) ∈ O(g(n)) then kf(n) ∈ O(g(n)) where k > 0

2) Sum Rule
f(n) ∈ O(h(n)) and g(n) ∈ (h(n)) then f(n) + g(n) ∈ O(h(n))
or
f(n) ∈ O(h(n)) and g(n) ∈ O(p(n)) then f(n) + g(n) ∈ O(h(n) + p(n))

3) Polynomial Rule
for non-negative constants a₀ …. a_k
a_kn^k + a_k-1n^k-1+ … + a₀n⁰ ∈ O(n^k)

4) Transitivity
f(n) ∈ O (g(n)) and g(n) ∈ O (h(n)) then f(n) ∈ O (h(n))

5) Recipical Rule
f(n) ∈ O(g(n)) then 1/g(n) ∈ O(1/f(n))

6) Log Domination Rule
log^kn ∈ O(n^d) where k > 0 and d > 0

7) Log Base Rule
log_an ∈ O(log_bn) where a ≠ 1, a > 0 and b ≠ 1, b > 0

8) Product Rule
f(n) ∈ O(h(n)) and g(n) ∈ O(p(n)) then f(n)g(n) ∈ O(h(n)p(n))

9) Constant Factor Rule
af(n) ∈ O(f(n)), ∀ positive constant a

10) Power Domination Rule
If f(n) is a polynomial with highest power k, then
f(n) ∈ O(n^k+a) ∀ positive constants a