Comparing Complexities

The Idea

The usual ranking runs O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Small inputs hide the gaps between them. Real data exposes those gaps immediately.

Real-World Example

A route planner that compares every pair of stops handles a ten-stop day just fine. Give it a thousand deliveries and it grinds for hours, while an O(n log n) planner answers before the driver finishes their coffee.

The Code

import math

n = 1_000_000
print(1)                      # O(1)       -> 1
print(int(math.log2(n)))      # O(log n)   -> 19
print(n)                      # O(n)       -> 1000000
print(int(n * math.log2(n)))  # O(n log n) -> ~19931568
print(n * n)                  # O(n^2)     -> 1000000000000
# Same input. Wildly different bills.