Constraint-Driven Algorithm Selection

Teach rough guidance:

n around a few hundred may permit O(n³) in some contexts.

n around thousands may suggest O(n²) or better.

n around 10⁵ often calls for O(n log n) or O(n).

n around 10⁶ often requires linear or near-linear work.

These are only heuristics; language, constants, multiple test cases, memory limits, and operation counts matter.

Constraint on n Operations if O(n²) O(n!), O(n·2ⁿ) permutations, backtracking

O(2ⁿ·n), meet in the middle O(2^(n/2)) O(n³) ≈ 1.25·10⁸ Floyd–Warshall, interval DP 2-D DP, all pairs 4·10¹⁰ (too slow) sorting, heaps, segment trees, binary search prefix sums, two pointers, linear scans ≥ 10⁹ (values) O(log n) or O(√n) binary search on answer, math, matrix exponentiation

A compiled language performs very roughly 10⁸–10⁹ simple operations per second; interpreted languages are often 10–100× slower. Multiply by the number of test cases, and check memory: 10⁷ long long values take 80 MB.

Quiz

? n ≤ 2·10⁵ and a 1-second limit. Which complexity is the usual target?
+ O(n log n) :: About 3.5·10⁶ operations.
- O(n²) :: 4·10¹⁰ operations.
- O(2ⁿ) :: Impossible.
- O(n³) :: Far too slow.

? n ≤ 20. What does that hint?
+ Exponential over subsets (2ⁿ·n) may be intended :: About 2·10⁷.
- An O(n) solution is required :: Small n allows more.
- Use a segment tree :: Unnecessary.
- The problem is trivial :: Not necessarily.

? Besides n, what affects whether a solution is fast enough? (select all that apply)
+ Number of test cases :: Total work adds up.
+ Constant factors and language :: Interpreted languages are slower.
+ Memory limits :: Big tables may not fit.
- The variable names :: No.