Big-O, Big-Omega and Big-Theta notation

Counting gives exact answers such as 3n² + 10n + 7 steps. For large n most of that expression stops mattering: at n = 1,000,000 the 3n² part is 3 × 10¹², while 10n + 7 adds about ten million more, a few millionths of the total. Asymptotic notation keeps the part that decides how the cost grows and drops the rest, including the constant factors that depend on the computer.

The three definitions

Running times are never negative, so the definitions below are written for functions f and g that take non-negative values. Each one says how f compares with a constant multiple of g from some point n₀ onwards; what happens for small n does not count.

• Big-O is an upper bound. f(n) = O(g(n)) when there are constants c > 0 and n₀ with $f(n) \le c \cdot g(n)$ for every n ≥ n₀: eventually f is at most a constant times g.
• Big-Omega is a lower bound. f(n) = Ω(g(n)) when there are constants c > 0 and n₀ with $f(n) \ge c \cdot g(n)$ for every n ≥ n₀: eventually f is at least a constant times g.
• Big-Theta is both at once. f(n) = Θ(g(n)) when f(n) = O(g(n)) and f(n) = Ω(g(n)), so there are constants c₁, c₂ > 0 and n₀ with $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for every n ≥ n₀: the two grow at the same rate.

The constants c and n₀ must be fixed numbers: they may depend on f and g, but not on n. Donald Knuth proposed Ω and Θ with these meanings for the analysis of algorithms, in “Big Omicron and big Omega and big Theta” (ACM SIGACT News, volume 8, number 2, pages 18–24); NIST’s Dictionary of Algorithms and Data Structures lists that paper on its pages for both symbols. The dictionary also notes that this Ω asks more than the older definition used in mathematics, which needed the inequality only for an endless sequence of values of n, not for every n from some point on.

The “=” in f(n) = O(g(n)) is a one-way statement, best read as “f is in O(g)”. So n = O(n²) is true, because n ≤ n² for every n ≥ 1, while n² = O(n) is false, and you cannot swap the two sides as you would in an equation.

A proof with explicit constants

Take f(n) = 3n² + 10n + 7 and prove that f(n) = Θ(n²).

• Upper bound. For n ≥ 1, 10n ≤ 10n² and 7 ≤ 7n². Adding these to 3n² gives f(n) ≤ 20n². So c = 20 and n₀ = 1 show that f(n) = O(n²).
• Lower bound. 10n + 7 is positive, so f(n) ≥ 3n² for every n. So c = 3 and n₀ = 1 show that f(n) = Ω(n²).
• Both hold, so f(n) = Θ(n²).

The constants are not unique. A smaller c needs a larger n₀: c = 4 works only once n² has outgrown 10n + 7, which first happens at n = 11. This program checks both bounds for every n up to a million, finds the first n₀ for three values of c, and prints how close f(n)/n² comes to 3:

def f(n):
    """A running time worked out by counting: 3n² + 10n + 7 steps."""
    return 3 * n * n + 10 * n + 7


N = 1_000_000
assert all(3 * n * n <= f(n) <= 20 * n * n for n in range(1, N + 1))
print(f"3n² <= f(n) <= 20n² for every n from 1 to {N:,}")

for c in (4, 5, 20):
    n0 = 1
    while f(n0) > c * n0 * n0:  # the first n where f(n) <= c·n² holds
        n0 += 1
    assert all(f(n) <= c * n * n for n in range(n0, N + 1))  # ... and it keeps holding up to N
    print(f"c = {c:>2}: f(n) <= {c}n² from n0 = {n0}")

for n in (10, 100, 1_000, 1_000_000):
    print(f"f({n:,}) / {n:,}² = {f(n) / (n * n):.6f}")

3n² <= f(n) <= 20n² for every n from 1 to 1,000,000
c =  4: f(n) <= 4n² from n0 = 11
c =  5: f(n) <= 5n² from n0 = 6
c = 20: f(n) <= 20n² from n0 = 1
f(10) / 10² = 4.070000
f(100) / 100² = 3.100700
f(1,000) / 1,000² = 3.010007
f(1,000,000) / 1,000,000² = 3.000010

A check up to a million is evidence, not proof; the algebra above is the proof, and it covers every n. The ratio f(n)/n² falls towards 3, the constant in front of the n² term: another sign that n² is the right comparison.

Keep the dominant term

Proofs like the one above all follow a few rules, which let you simplify a running time in one line:

1. Drop constant factors. 5n² = Θ(n²) and n/2 = Θ(n).
2. Drop lower-order terms. n² + 1000n = Θ(n²), because 1000n ≤ n² once n ≥ 1000.
3. A polynomial is Θ of its highest power. 4n³ − 2n² + 9 = Θ(n³).
4. The base of a logarithm does not matter. log₂ n and log₁₀ n differ by the constant factor log₂ 10, so both are Θ(log n), and the base is left out (the logarithm calculator changes base for you when a count needs an actual number).
5. The base of an exponential does matter. 3ⁿ / 2ⁿ = 1.5ⁿ grows without limit, so 3ⁿ is not O(2ⁿ).

import math

print("log2(n) / log10(n), for n = 10, 1,000 and 10**9:")
print(" ", ", ".join(f"{math.log2(n) / math.log10(n):.5f}" for n in (10, 1_000, 10**9)))

print("3**n / 2**n, for n = 10, 100 and 1,000:")
print(" ", ", ".join(f"{3**n / 2**n:.4g}" for n in (10, 100, 1_000)))

log2(n) / log10(n), for n = 10, 1,000 and 10**9:
  3.32193, 3.32193, 3.32193
3**n / 2**n, for n = 10, 100 and 1,000:
  57.67, 4.066e+17, 1.234e+176

The first line is the same for every n: the two logarithms are always the same multiple of each other. The second line keeps growing, which is why 2ⁿ and 3ⁿ belong to different classes even though both are called exponential.

From slowest to fastest, the growth rates you will meet most often in this track are:

Each one is o(the next), in the sense defined at the end of this lesson.

Misuses to avoid

“Big-O means the worst case”

It does not. Big-O bounds a function, and the best case, the worst case and the average case of an algorithm are three different functions of n. Each can be described with O, Ω or Θ. Insertion sort shows the difference:

import random


def insertion_sort(items):
    """Sort a copy of items, and count the comparisons between two items."""
    a = list(items)
    comparisons = 0
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if a[j] <= x:
                break
            a[j + 1] = a[j]  # shift the larger item one place right
            j -= 1
        a[j + 1] = x
    assert a == sorted(items)
    return comparisons


rng = random.Random(11)
print(f"{'n':>6} {'sorted input':>13} {'random input':>13} {'reversed input':>15}")
for n in (10, 100, 1_000):
    values = list(range(n))
    shuffled = rng.sample(values, n)
    counts = insertion_sort(values), insertion_sort(shuffled), insertion_sort(values[::-1])
    print(f"{n:>6,} {counts[0]:>13,} {counts[1]:>13,} {counts[2]:>15,}")

     n  sorted input  random input  reversed input
    10             9            38              45
   100            99         2,436           4,950
 1,000           999       245,288         499,500

On sorted input each new item needs one comparison, n − 1 in all; on reversed input it is compared with everything before it, n(n − 1)/2 in all; random input lands near n²/4. So the precise statement is: insertion sort’s worst case is Θ(n²) and its best case is Θ(n). “Insertion sort is O(n²)” is true, because no input needs more than quadratic time, but it is not the same claim as “the worst case is Θ(n²)”, and “insertion sort is Θ(n²)” is false for sorted input.

Dropping a second input

When the cost depends on two sizes, keep both. Checking every name of a list a against a list b with in:

def common_names(a, b):
    """Names that are in both lists, and how many comparisons the `in` tests made."""
    comparisons = 0
    both = []
    for name in a:
        for other in b:  # what `name in b` does on a list
            comparisons += 1
            if name == other:
                both.append(name)
                break
    return both, comparisons


for n, m in ((1_000, 10), (10, 1_000), (1_000, 1_000)):
    a = [f"guest{i}" for i in range(n)]
    b = [f"member{i}" for i in range(m)]  # no names in common: every `in` checks all of b
    _, steps = common_names(a, b)
    print(f"n = {n:>5,}, m = {m:>5,}: {steps:>9,} comparisons = n × m")

n = 1,000, m =    10:    10,000 comparisons = n × m
n =    10, m = 1,000:    10,000 comparisons = n × m
n = 1,000, m = 1,000: 1,000,000 comparisons = n × m

The cost is O(n · m) for n = len(a) and m = len(b), not O(n²): the first two lines make the same 10,000 comparisons with very different n. In the same way, a graph algorithm that looks at every vertex and every edge once is O(V + E), and comparing n strings of length L each is O(n · L).

A true bound that says too little

3n + 4 = O(n²) is true, and NIST’s dictionary uses it as an example, but it hides the fact that the cost is linear. Give the tightest bound you can prove, and use Θ when you have both directions.

Forgetting the constants exist

Big-O hides constant factors, and for small inputs they can decide. An algorithm that takes 100n steps is slower than one that takes n² steps for every n below 100, although Θ(n) beats Θ(n²) in the long run. The first lesson of this track measured such a constant factor.

Little-o, little-omega and the limit test

The strict versions say that one function grows strictly slower or faster than another:

• f(n) = o(g(n)) when, for every constant c > 0, f(n) < c·g(n) from some n₀ on (n₀ may depend on c). f becomes negligible next to g.
• f(n) = ω(g(n)) when g(n) = o(f(n)).

The CS2023 curriculum lists both among the complexity topics beyond Big-O, Big-Omega and Big-Theta. The quickest way to compare two functions is often the limit of their ratio: work out $L = \lim_{n \to \infty} f(n) / g(n)$ and read off the answer.

• L = 0: f(n) = o(g(n)), so f grows strictly slower.
• L is a constant greater than 0: f(n) = Θ(g(n)), so they grow at the same rate.
• L is infinite: f(n) = ω(g(n)), so f grows strictly faster.

For f(n) = 3n² + 10n + 7 and g(n) = n² the ratio tends to 3, as the program above showed, so f(n) = Θ(n²). For n log n against n², the ratio is (log n)/n, which tends to 0, so n log n = o(n²). If the ratio has no limit at all, the test says nothing, and you are back to the definitions.

Key takeaways

• f(n) = O(g(n)) means f(n) ≤ c·g(n) for all n ≥ n₀, for some fixed constants c and n₀; Ω is the matching lower bound and Θ is both.
• A Θ proof names its constants: 3n² ≤ 3n² + 10n + 7 ≤ 20n² for every n ≥ 1.
• Simplify by dropping constant factors and lower-order terms; logarithm bases do not matter, exponential bases do.
• O is a bound, not a case: state which case (best, worst, average) you are bounding, and keep every input size that matters.
• If f(n)/g(n) tends to 0, f is o(g); to a positive constant, Θ(g); to infinity, ω(g).