Big-O describes an upper bound on how T(n) grows. We drop constants and slower terms: 3n + 8 is O(n). Ω is a lower bound. Θ is both — tight.

Goal

Classify a few T(n) expressions and print growth for n = 4, 8, 16.

Drop constants

def T_linear(n):
    return 3 * n + 8

def T_quad(n):
    return n * n + 10 * n

for n in (4, 8, 16, 32):
    print(n, "linear", T_linear(n), "quad", T_quad(n))

When n doubles, linear about doubles; quadratic about quadruples.

Names we use

def log2(n):
    k = 0
    while n > 1:
        n //= 2
        k += 1
    return k

n = 16
print("O(1)", 1)
print("O(log n)", log2(n))
print("O(n)", n)
print("O(n log n)", n * log2(n))
print("O(n^2)", n * n)

Common order, slowest last: 1, log n, n, n log n, n², 2ⁿ.

Worst case

def scan(xs, target):
    steps = 0
    for x in xs:
        steps += 1
        if x == target:
            return steps
    return steps

xs = ["Nairobi", "Mombasa", "Kisumu", "Nakuru"]
print("hit first", scan(xs, "Nairobi"))
print("miss", scan(xs, "Eldoret"))

Best case for this scan is Θ(1) (first item). Worst case is Θ(n) (miss). Big-O for the algorithm usually means worst case unless we say otherwise.

Pitfall

O(n²) is also O(n³) — Big-O is an upper bound, not “exactly”. When we mean tight, we say Θ(n²).