Big-O & Complexity

8 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   Big-O counts how the number of steps grows with the input size n. Constants and small terms drop: 3n + 5 → O(n); n² + 100n → O(n²).

   #1
2. ↯use it when

   Before coding, turn the constraints into a budget. While explaining, give time and space, each with a one-line reason.

   #2
3. O( )cost

   At n = 10⁶: log n ≈ 20 · n log n ≈ 2·10⁷ · n² = 10¹². A judge allows roughly 10⁸ simple steps per second.

   #3
4. { }template

   Loops in sequence add (O(n + m)). Nested loops multiply (O(n·m)). A loop that halves is O(log n). Recursion = calls × work per call.

   #4
5. !trap

   Hidden loops: list.contains, list.remove(0), substring, s += x are O(n). Inside a loop they quietly make O(n²).

   #5
6. !trap

   "HashMap is O(1)" — say average. And the recursion stack is space: n waiting calls = O(n), even with no arrays.

   #6
7. ✦pro tip

   Amortized O(1): ArrayList.add sometimes copies everything, but capacity grows ~1.5×, so n adds cost O(n) in total.

   #7
8. ✦pro tip

   An inner pointer that never moves back (two pointers, sliding window) is O(n) overall, not O(n²). Count pointer moves.

   #8

Shaky on a card? Open the chapter or flip its recall cards.