Big-O complexity

How runtime grows with input size. O(1) constant, O(n) linear, O(n²) quadratic, O(log n) logarithmic.

Code example

# O(1) — constant
nums[0]

# O(n) — linear
for x in nums: process(x)

# O(n²) — quadratic (nested loop over same n)
for x in nums:
  for y in nums: compare(x, y)

How it works

Big-O describes how an algorithm's runtime grows as the input grows. O(1) doesn't grow at all (hash lookup). O(log n) grows slowly (binary search — doubling the input adds one step). O(n) grows linearly (single loop). O(n²) grows quadratically (nested loop). For n=1000: O(n) is 1000 ops, O(n²) is 1,000,000 ops. The notebook's package hint map is a dict — O(1) lookup vs O(n) list scan matters when you're checking 60+ packages per cell execution.