Will it be fast enough?
Estimate an approach's work and compare it with what fits in a second. About 8 minutes.
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.
log n: halving a million down to 1 takes about 20 steps. Instant.
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.
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_000A list can hold up to 1,000,000 values. Which approach fits in about a second?
- AO(n): one pass
- BO(n²): check every pair
Show the answer
O(n): one pass. 1,000,000 steps is far under 100 million.
Fits in a second?
You get n and a growth name: "log n", "n", "n log n" or "n^2". Estimate the work: log n is the number of halvings from n down to 1 (as in the last step), n is n, n log n is n times the halvings, and n^2 is n × n. Return true if the work is at most 100,000,000, and false otherwise.
n = 10000, growth = "n^2" → true
1 ≤ n ≤ 1,000,000,000 · n × n can be huge, so compute it in a long