Linear and binary search in the Search post were both correct, yet their speeds were very different. What exactly does “fast” mean?
Could we just run them and time it? The same program takes different amounts of time depending on how fast the CPU is or whether the data was in the cache. Measured time isn’t a property of the algorithm alone.
So instead of time, we count operations. For search, that’s the number of values checked. If there are n items, linear search checks n times, and binary search checks about log₂ n times, the number of times n can be halved until it reaches 1.
Writing the number of operations as a formula T(n) in the input size n is called time complexity.
But even at the same size, the count depends on the input. Linear search takes 1 check if the value is at the front, and n if it isn’t there at all. So we usually count the unluckiest case, the worst case. Then we can promise it never takes longer whatever the input, and the worst case happens often, as when the value just isn’t there. For algorithms whose worst case is rare, people sometimes quote the average separately.
The exact T(n) easily gets complicated. Selection sort in the Algorithms post has T(n) = ½n² − ½n. Let’s see what happens if we drop the small term ½n and the ½ in front.
As n grows, the share ½n takes in the exact formula approaches 0%. A number that doesn’t depend on n, like the ½ in front (a constant), doesn’t affect how many times over the count grows as n increases. So we keep only the fastest-growing term, drop the constant, and write just its shape for large n. This is called big-O notation: selection sort is O(n²), linear search O(n), and binary search O(log n).
Suppose the computer does a billion operations per second, and compare the times.
Raise n to a billion.
Only O(n²) takes decades, and O(log n) is still about 30 even at a billion. When the count stays the same whatever n is, like reading slot i of a array, it’s O(1).
Making the computer 10 times faster only changes the constant in front, so O(n²) still takes years.
In this part we wrote tasks as algorithms, saw that the same job can run at different speeds depending on the algorithm and data structure, and measured that speed with time complexity. But a few demo runs can’t promise an algorithm is right for every input, and reasoning about the average means counting every case and working out probabilities. So the next part covers the math of proving, counting, and dividing: discrete mathematics. The first post is Proof.
In big-O notation, how many times does the code below increase count? for j in range(i) runs i times, and // is integer division.
count = 0
i = n
while i >= 1:
for j in range(i):
count += 1
i = i // 2