Measuring speed: Big-O notation

How do you say one algorithm is faster than another? Seconds are a poor measure: the same code runs at different speeds on a laptop and a server, and the time changes with the input. Instead we count how many basic steps the algorithm does for an input of size n, and we ask one question: as n grows, how fast does the work grow?

Big-O notation is the short way to write that growth. O(n) means “the work grows in proportion to n”: twice the data, about twice the work. O(n²) means twice the data, four times the work.

The common growth rates

Rule 1: drop the constants

Big-O describes the shape of growth, not the exact count. An algorithm that does 3n + 5 steps is O(n). One that loops twice over the data (2n) is still O(n). Constants depend on the machine and compiler; the shape does not.

1// 2n steps → O(n)2int min = int.MaxValue, max = int.MinValue;3foreach (int x in data) if (x < min) min = x;4foreach (int x in data) if (x > max) max = x;5 6// n/2 steps → still O(n)7for (int i = 0; i < data.Length / 2; i++)8    (data[i], data[^(i + 1)]) = (data[^(i + 1)], data[i]);

Rule 2: keep only the biggest term

If an algorithm does n² + n + 100 steps, the n² part dominates as n grows (for n = 10,000 it is 100,000,000 against 10,100). So it is O(n²).

1// Part 1: O(n)2foreach (var beam in beams) Validate(beam);3 4// Part 2: O(n²): every pair5for (int i = 0; i < beams.Length; i++)6    for (int j = i + 1; j < beams.Length; j++)7        CheckClash(beams[i], beams[j]);8 9// Total: O(n + n²) = O(n²)

Rule 3: different inputs get different letters

If a method works on two collections of unrelated sizes, do not call both “n”. Looping over a and then over b is O(a + b). Looping over b inside a loop over a is O(a × b).

1// O(a + b)2foreach (var c in columns) Draw(c);3foreach (var b in beams) Draw(b);4 5// O(a × b)6foreach (var c in columns)7    foreach (var b in beams)8        if (Touches(c, b)) Connect(c, b);

Best, average and worst case

The same algorithm can do different amounts of work for different inputs of the same size. Linear search finds the first element in 1 step (best case), but a missing element needs n steps (worst case). On average it checks about half.

When people say “binary search is O(log n)” without saying which case, they mean the worst case. It is a promise: no input of size n will take longer.

Big-O, Big-Ω and Big-Θ

• Big-O (O): an upper bound. “It grows no faster than this.”
• Big-Omega (Ω): a lower bound. “It grows at least this fast.” Any comparison sort is Ω(n log n).
• Big-Theta (Θ): both at once. “It grows exactly like this.” Merge sort is Θ(n log n).

In everyday conversation and interviews, people say Big-O and mean the tight bound. That is fine; just know the other two exist.

1int First(int[] a) => a[0];                       // O(1)2 3int Sum(int[] a)                                   // O(n)4{5    int s = 0;6    foreach (int x in a) s += x;7    return s;8}9 10bool HasPairWithSum(int[] a, int target)           // O(n²)11{12    for (int i = 0; i < a.Length; i++)13        for (int j = i + 1; j < a.Length; j++)14            if (a[i] + a[j] == target) return true;15    return false;16}17 18int SumFirstTen(int[] a)                           // O(1): at most 10 steps19{20    int s = 0;21    for (int i = 0; i < Math.Min(10, a.Length); i++) s += a[i];22    return s;23}