Time complexity from the constraints

Short answer. Read the input size first, because it tells you which complexity is allowed. A computer does about 100 million simple operations per second. So n up to 20 allows every subset, n up to 5,000 allows n², n up to 100,000 needs n log n, and n near a billion needs a log or a formula.

Everything below follows from that one number, and from what time complexity means.

The table

• n up to 10: anything. Try every permutation, that is 3.6 million.
• n up to 20: every subset is a million. Bitmask solutions live here and almost nowhere else.
• n up to 500: n cubed is fine. Floyd-Warshall, interval dynamic programming.
• n up to 5000: n squared is fine. Every pair, most string DP.
• n up to 100000: you need n log n. Sorting, heaps, binary search inside a loop, balanced trees.
• n up to 10 million: one pass, and keep it cheap. Windows, prefix sums, counting.
• n around a billion: you cannot touch every element. Expect a log, a formula, or binary search on the answer.

Five minutes of memorising. It removes most wrong turns before they happen.

The last row: binary search on the answer.

Read it backwards

Go from the bound to the shape of the code.

n log n usually means one sort. Or one loop with a binary search inside.

Two nested passes over 100 thousand items fail before you write them. To check a function you already wrote, the Big O calculator measures it.

Forwards, you write the quadratic version and find out at submit time.

Backwards, you skip that half hour.

The other numbers

Input size gets the attention. Three more lines carry as much.

The value range. "Values up to 10 to the sixth" means an array of that size and direct counting.

"Up to 10 to the ninth" means you cannot. Now it is a hash map or coordinate compression.

The alphabet. "Lowercase English letters" means 26 slots. A fixed array replaces the hash map and the constant drops.

A fixed array also makes the space O(1). Worth saying out loud.

The memory limit. 256 MB is about 64 million 4-byte integers.

A table of 100 thousand by 100 thousand will not fit. However elegant the recurrence is.

Interviews rarely give you any of this

Competitive problems state the bounds. Interviewers usually do not.

Asking about constraints is one of the best questions to ask.

"How large can this array be?" "Can the values be negative?" Four seconds each.

Both change the answer. Asking shows the reflex being scored.

Being told it does not matter still needs a stated assumption. Say what you are assuming and continue.

Your solution is correct under a stated assumption. That beats being quietly wrong.

One of five ideas in why algorithm problems are hard.

When the bound looks strange

An odd constraint is a hint. Someone left it for you.

n up to 20 with an unlimited value range is a bitmask problem announcing itself.

A tiny n next to many queries means precompute once, answer fast.

Exactly 10 to the fifth next to a 1 second limit means n log n. Nothing slower.

Those numbers are chosen deliberately. Reading them is free information.

Where this is drilled

AlgoPath puts constraint reading in step 09, "Big-O: a name for how fast the work grows", before the first pattern.

Every recognition prompt after it carries the bounds, for this reason.

The first 33 steps are free.

The notation behind the table is in Big O explained simply.