About 100 million a second
A rough rule: a computer does about 100,000,000 simple steps in a second, a little like a runner with a known pace. A judge typically gives you a second or two, so an approach whose work stays under 100 million is safe.
Before you write any code, you can estimate whether an idea is fast enough by counting its steps.
Up to 100,000,000 steps: fits comfortably in time.
n = 1,000,000 · budget: about 100,000,000 steps a second
stepsfits?
log n
20
yes
n
n log n
n²
log n: halving a million down to 1 takes about 20 steps. Instant.
Move 1 of 5
Plug n into the growth
Big-O names describe how work grows. To estimate, put the real n in: O(n) is n steps, O(n²) is n × n, O(log n) is the number of halvings, and O(n log n) is n times that. Then compare with the budget.
It is like checking a road trip: distance divided by speed tells you whether you'll arrive in time.
n = 10,000: O(n²) is 100,000,000: just fits.
n = 1,000,000: O(n²) is a trillion: far too slow.
halvings = 0
m = n
while m > 1:
m //= 2
halvings += 1
work = {"log n": halvings, "n": n,
"n log n": n * halvings,
"n^2": n * n}
return work[growth] <= 100_000_000