Estimating Time Limits

Modern computers do about $10^8$ simple operations per second.

Rule of thumb for 1-second limit:

• $O(n)$: $n \leq 10^8$
• $O(n \log n)$: $n \leq 10^7$
• $O(n^2)$: $n \leq 10^4$
• $O(n^3)$: $n \leq 500$
• $O(2^n)$: $n \leq 25$
• $O(n!)$: $n \leq 10$

Example: If $n = 20$ and you need $O(2^n)$, that's $\approx 10^6$ operations. Should pass in well under a second.

Always check constraints first. If brute force fits, use it. Simple code has fewer bugs.