Comparing Complexities

Big-O: lesson 5 of 5

O(n log n) beats O(n²) long before you notice.

Lesson 5 of 5 · 5 min

Step 1 of 7

at n =1,000,000

Same axes, same input. Watch how far apart the classes drift before n even gets interesting.

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.

Your turn

Put the steps in the right order.

O(n²)
O(1)
O(n log n)
O(log n)
O(n)

Mini quiz

1 / 3

Comparing Complexities