Big-O and Reading Constraints

In an interview (and on every judge) your code is graded on two things: is it correct, and is it fast enough for the biggest input allowed?

Big-O describes how the number of steps grows as the input size n grows. You keep the fastest growing term and drop constants: 3n² + 5n + 7 is just O(n²).

The classes you'll meet, fastest to slowest:

• O(1): constant (nums[i], average dict lookup for fixed-size keys)
• O(log n): halve the problem each step (binary search)
• O(n): one pass over the input
• O(n log n): sorting, or n heap operations
• O(n²): every pair (nested loops)
• O(2ⁿ): every subset (backtracking)

Reading Big-O off code:

• Steps one after another add: O(n) + O(n) is still O(n).
• Independent nested loops multiply: a loop of m inside a loop of n is O(nm). If both sizes are n, that's O(n²).
• An inner loop that starts at i + 1 still counts: (n−1) + (n−2) + … + 1 = n(n−1)/2, which is O(n²).
• Halving a value until it reaches 1, or doubling from 1 until it reaches n, takes O(log n) steps.
• Nested syntax alone doesn't prove O(n²). If an inner pointer only moves forward across the whole input, count its total moves: at most n.
• A built-in call counts as its own cost: max(nums) inside a loop is a hidden inner loop (next lesson).

Recursion: add the work across all calls. If every call does the same amount of work, multiply the number of calls by that amount. Draw the call tree and count it.

• One recursive call on n − 1 with O(1) work: n calls, O(n).
• One call on n / 2 with O(1) work per call: O(log n).
• Two calls on n − 1 with O(1) work per call: the tree doubles each level, O(2ⁿ).
• Two calls on half the input plus a linear merge: O(n) work per level and O(log n) levels, so O(n log n), as in merge sort.
• With memoization, each distinct argument is computed once: (number of states) × (work per state).

Recursion also uses space: every waiting call sits on the call stack, so depth d costs O(d) memory.

Time vs space. Auxiliary space counts peak extra memory beyond the input and required output. State that convention; output still takes real memory. Returning n answers needs O(n) output space even with O(1) working space.

• Two index variables: O(1) space.
• A set of everything seen: O(n) space.
• Recursion depth n: O(n) stack space.

The most common trade in interviews is spending O(n) memory (a set or dict) to turn O(n²) time into O(n) time.

Amortized O(1). list.append is O(1) amortized: the list keeps spare capacity, and when it runs out it grows by a proportion of its size and copies everything. Those copies are rare enough that n appends cost O(n) in total.

Constraints are a hint. Before thinking about an algorithm, read the limit on n. These are rough starting targets, not timing promises. Python loop bodies, built-ins, hardware and time limits differ; Pyodide also has browser overhead. Work backwards, then test a large input:

So "1 ≤ n ≤ 10⁵" is the problem setter telling you: avoid comparing every pair; look for O(n log n) or better. A value bound of 10⁹ is different from having 10⁹ input elements. Read every dimension: an r × c grid has rc cells.