Let’s think it through · Start with a story
The robot is about to compare every pair among 100,000 numbers. The girl estimates the count first and sees that it could approach ten billion operations.
Break down the process
- Input sizen = 100,000
- Two complete passesn multiplied by n
- Operation count10,000,000,000
- DecisionLook for ways to reduce the work
First estimate the number of key operations, then test in the actual environment.
Quadratic growth makes large inputs difficult to handle, even when each operation is fast.
01What does TLE mean?
TLE (Time Limit Exceeded) means a program ran longer than the time allowed by the problem.
The answer logic might be correct; the program may simply be too slow.
02Step 1: Check the maximum input size
For example:
n <= 200000Estimate complexity using the maximum n, not the small n in a sample.
03Step 2: Estimate the algorithmic complexity
O(n)
About 2×10⁵ units of work.
O(n log n)
Still common and often practical.
O(n²)
About 4×10¹⁰ operations; usually risky.
O(2ⁿ)
Grows explosively even for moderately sized n.
04Can you strictly assume “1 second = 100 million operations”?
No. Do not treat that as an exact rule.
05Is complexity estimation still useful?
Very much so. It helps rule out approaches that are obviously impractical.
For example, with n = 200,000, an O(n²) algorithm involves tens of billions of operations. Even without precise timing, that is enough to recognize a serious risk.
06What else should you consider besides time?
You also need to consider memory.
For example, creating an n × n matrix of integers may cause an MLE (Memory Limit Exceeded) when n is large.
07Can recursion have an impact?
Yes. The algorithm’s total runtime may be acceptable, but excessive recursion depth can still exhaust the call stack.
08How do you build the habit of estimating in contests?
What you have learned
- TLE means the program exceeded the time limit.
- Estimates must use the maximum input size.
- Complexity is the first tool for judging whether an approach is feasible.
- “Operations per second” is only a rough guide, not a fixed formula.
- Also consider memory, I/O, and recursion depth.
Next: From Problem to AC: Solving a Contest Problem from Start to Finish
Your turn
If n grows from 1,000 to 10,000, by what factor does n² grow?
Have an answer? Click to see the explanation
By a factor of 100. The input size grows by 10, so the quadratic workload grows by 10 × 10.