Quiz (2)
Quiz: Time Complexity of Code
Read each snippet's shape and give its time complexity. The first five read straight off the shape; the last three are the ones that trip strong candidates — a false O(log n), a false O(n log n), and an amortized bound. Recompute before peeking.
1. A single loop for (i=0; i<n; i++) doing O(1) work per iteration?
Answer: O(n) — n iterations, constant work each.
2. Two nested loops where the inner runs 0..i (triangular)?
Answer: O(n²) — total iterations = 0+1+…+(n−1) = n(n−1)/2, and constants/lower terms drop to n².
3. while (n > 1) n = n / 2;
Answer: O(log n) — each step halves n, so it runs about log₂n times.
4. Two sequential (not nested) loops, one to n and one to m?
Answer: O(n + m) — sequential work adds; only nested loops multiply.
5. Binary search over a sorted array of n elements?
Answer: O(log n) — each comparison discards half the remaining range.
6. Trap: is while (n > 1) n = n − 1; also O(log n)?
Answer: No — O(n). The log comes from halving (n/2 shrinks the remaining size multiplicatively, so it takes log₂n steps). Decrementing shrinks it additively, so it takes n steps. The rule to internalise: how many times can you apply the shrink step before hitting the base? Divide-by-c → log₃cn; subtract-by-c → n/c. This is the single most common false O(log n) claim in interviews.
7. Count: for (i = 1; i <= n; i *= 2) { for (j = 0; j < i; j++) work; } — is this O(n log n)?
Answer: No — O(n). The outer loop runs about log₂n times with i = 1, 2, 4, …, ≤ n, but the inner loop runs i times, not n times. Total work = 1 + 2 + 4 + … + n = 2n − 1 (a geometric series), which is O(n). For n = 8: 1+2+4+8 = 15 = 2·8−1. The trap is multiplying “log n levels” by the largest single level’s n → O(n log n); you must sum the levels, and a geometric series is dominated by its largest term, so the total is Θ(n). (Contrast: if the inner bound were fixed at j < n on every pass, it really would be O(n log n).)
8. Amortized: you append n items one at a time to a dynamic array that doubles its capacity when full; a single append can trigger an O(n) copy. Total cost across the n appends? Per-append cost?
Answer: Total O(n); amortized O(1) per append. Across n appends the resizes copy 1 + 2 + 4 + … + n ≈ 2n elements in total (geometric series again), so all appends together are O(n). The trap is “one append is O(n) and there are n of them → O(n²)”: that double-counts, because the expensive doubling copies are exponentially rare. Note amortized ≠ average-case — it is a worst-case guarantee spread over a sequence of operations, holding even against an adversary. This is why ArrayList/vector/Python list append is quoted as O(1).
Self-check quiz authored for this guide — Grokking Algorithm Complexity & Big-O.
🤖 Don't fully get this? Learn it with Claude
Stuck on Quiz (2)? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Quiz (2)** (DSA) and want to truly understand it. Explain Quiz (2) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Quiz (2)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Quiz (2)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Quiz (2)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.