When constants win
For small n, a slower-growing algorithm with a big constant can lose. About 8 minutes.
Big-O hides the constant
Big-O tells you who wins in the long run, not today. One shop may charge a small fee on every item and another a large fee once, and which is cheaper depends on how much you buy.
O(n) code might really do 100 steps per item, and O(n²) code 1 step per pair. At n = 10 that's 1,000 steps against 100: the O(n²) code is faster.
At n = 10, algorithm 1 does 100 × 10 = 1,000 steps.
Estimate with real numbers
Work out each algorithm's steps as its constant times its growth at the actual n, with log n as the number of halvings down to 1. Then compare the two numbers directly.
That way the answer reflects what really happens at your input size, not just the long-run trend.
halvings = 0
m = n
while m > 1:
m //= 2
halvings += 1
work = {"1": 1, "log n": halvings, "n": n,
"n log n": n * halvings,
"n^2": n * n}
first = c1 * work[g1]
second = c2 * work[g2]
return 1 if first <= second else 2At n = 50, which does less work: 100 × n or 1 × n²?
- A1 × n² (2,500 steps)
- B100 × n (5,000 steps)
- CThey're equal
Show the answer
1 × n² (2,500 steps). 100 × 50 = 5,000, and 50² = 2,500.
Which does less work?
Algorithm 1 does c1 × g1(n) steps and algorithm 2 does c2 × g2(n) steps, where each growth is one of "1", "log n", "n", "n log n" or "n^2", and log n means the number of halvings from n down to 1. Return 1 if algorithm 1 does no more work than algorithm 2, and 2 otherwise.
n = 10, c1 = 100, g1 = "n", c2 = 1, g2 = "n^2" → 2
1 ≤ n ≤ 1,000,000 · 1 ≤ c1, c2 ≤ 1,000 · use longs