Big-O in practice: will my solution pass the time limit?

Before you write code in an online assessment, look at the limits on n. They tell you which complexity the setter expects.

Rule of thumb

A typical judge runs roughly 10⁷ to 10⁸ simple operations per second, and less in Python. Plug the largest n into your complexity:

• n up to about 10 to 12: O(n!) or O(2ⁿ · n), such as trying every permutation or subset.
• n up to about 20 to 25: O(2ⁿ), such as bitmask brute force.
• n up to about 500: O(n³).
• n up to about 5,000: O(n²).
• n up to about 10⁶: O(n log n) or O(n), such as sorting, a heap, or two pointers.
• n up to 10⁹ or more: O(log n) or O(1), such as binary search or a formula.

Counting, not guessing

const n = 1000;
let pairs = 0;
for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) pairs++;
console.log('nested pairs:', pairs);
let halvings = 0;
for (let k = n; k > 1; k = Math.floor(k / 2)) halvings++;
console.log('halving steps:', halvings);

nested pairs: 499500
halving steps: 9

• A loop over all pairs runs n(n − 1)/2 times. That is about half a million for n = 1,000, but about 5 × 10⁹ for n = 10⁵, which is far too slow.
• Halving n each step takes about log₂ n steps: 9 for 1,000 and only about 30 even for a billion. That is why binary search is so fast.

Habits

• Drop constants and smaller terms: O(3n + 50) is O(n), and O(n² + n) is O(n²).
• Count the cost of library calls: sorting is O(n log n), and indexOf, includes or list.contains inside a loop adds another factor of n.
• State the time and space complexity aloud after every solution in an interview. Interviewers expect it.