Module 2

Big-O notation

Big-O answers one question: as the input grows, how fast does the work grow? It deliberately ignores constants and small terms — O(3n + 40) is just O(n) — because for large inputs the growth shapedominates everything else. That's also why an O(n log n) algorithm with ugly constants eventually beats a tidy O(n²) one, every time, at some input size.

Three reading rules cover most code: sequential steps add (and the bigger term wins), nested loops multiply (a loop inside a loop over n is n·n), and halving is log — any loop that discards half the remaining input each pass runs log₂ n times. When someone says O(n) they conventionally mean the worst caseunless they say otherwise; it's worth stating which case you're quoting.

ClassNameCanonical examples
O(1)constanthash-map get/put, array index, stack push/pop
O(log n)logarithmicbinary search, balanced-BST operations
O(n)linearone scan: max, sum, building a hash map
O(n log n)linearithmicgood comparison sorts: merge sort, heapsort, quicksort (expected)
O(n²)quadraticnested loops over the same input: all pairs, bubble sort
O(2ⁿ)exponentialall subsets, naive Fibonacci — recursion that branches without memoization

🎛 Growth-rate explorer

ComplexityOperations at nWall-clock (10⁸ ops/s)Verdict
O(1)1.0< 1 msfine
O(log n)10.0< 1 msfine
O(n)1.0k< 1 msfine
O(n log n)10.0k< 1 msfine
O(n²)1.0M10 msfine
O(2ⁿ)2^1,000forget ittoo slow

Rule of thumb in a timed setting: ~10⁸ simple operations per second. Slide n up and watch O(n²) die at n = 10⁵ while O(n log n) stays comfortable at 10⁸ — that gap is what the interviewer means by “can you do better?”

Worked example — reading the complexity off the code

def has_duplicate(items):
    seen = set()               # O(1) — setup
    for x in items:            # runs n times
        if x in seen:          #   O(1) average — hash lookup
            return True
        seen.add(x)            #   O(1) average
    return False               # total: O(n) time, O(n) space

The sorting alternative — sort, then scan neighbors — is O(n log n) time but O(1) extra space. Neither is “right”: naming the time/space trade between them is the answer.

Two refinements worth knowing cold

Amortized cost.A dynamic array's append is usually O(1) but occasionally O(n) when it resizes; spread over many appends the average is O(1) — “amortized O(1)”. Same story for hash-map inserts across resizes.

Space counts too.Recursion depth is space (the call stack), a memo table is space, and “can you do it in-place?” is a space question. Quote both: “O(n) time, O(1) extra space.”

Say it out loud

  • “This is O(n²) from the nested loop — the repeated work is the inner search, so a hash set should get us to O(n).”
  • “n can be 10⁵ here, so quadratic is ~10¹⁰ operations — too slow. The target is O(n log n) or better.”
  • “Append is amortized O(1) — occasional resizes, constant on average.”
← MethodNext: Core data structures →