Complexity Analysis Concepts

Complexity analysis describes how much more time and memory an algorithm needs as its input grows. A measurement like "this takes 0.3 seconds" depends on the machine, the language and the data, but a property like "doubling the input quadruples the running time" holds almost everywhere. Complexity analysis is about that shape of growth. This chapter covers input size, asymptotic notation (O, Ω, Θ), best, average and worst cases, and the vocabulary used in the rest of the guide.

Input size n

Analysis starts by deciding what "size" means. For a list it is the number of elements, for a string its length. Graphs usually need two variables, V vertices and E edges, and comparing two strings uses both lengths m and n.

Be careful with functions that take a single integer. The input size is the number of digits (bits) needed to write the number, not its value. Trial division up to √n is O(√n) in the value n, but O(2^(b/2)), exponential, in the bit length b.

Asymptotic notation: O, Ω, Θ

• Big-O (upper bound): f(n) = O(g(n)) if there are positive constants c and n0 such that f(n) ≤ c·g(n) for every n ≥ n0. f grows no faster than g.
• Big-Omega (lower bound): f(n) = Ω(g(n)) if f(n) ≥ c·g(n) under the same conditions. f grows at least as fast as g.
• Big-Theta (tight bound): f(n) = Θ(g(n)) if both hold. f grows at the same rate as g.

For example, f(n) = 3n² + 5n + 20 satisfies 3n² ≤ f(n) ≤ 28n² for n ≥ 1, so it is Θ(n²). Saying O(n³) is technically true but loose. In everyday speech, "this is O(n²)" usually means Θ.

We drop constants and lower-order terms because the highest-order term dominates as n grows. You can check the ratio yourself:

def f(n):
    return 3 * n * n + 5 * n + 20

for n in (10, 100, 1_000, 10_000):
    print(n, f(n), round(f(n) / (n * n), 4))
# 10 370 3.7
# 100 30520 3.052
# 1000 3005020 3.005
# 10000 300050020 3.0005

The ratio approaches 3, so f eventually behaves like a constant multiple of n². That constant changes with hardware and implementation, so the notation leaves it out.

Cases and bounds are different questions

A common misconception is "O means worst case, Ω means best case". They answer two separate questions:

• Which inputs are we looking at? Best case, average case, worst case.
• How do we describe that running time? Upper bound O, lower bound Ω, tight bound Θ.

Linear search finishes after one comparison when the target is first (best case ) and needs n comparisons when it is last or missing (worst case ). If the target is equally likely to be anywhere in the list, the average is comparisons, which is still .