Quiz
Quiz: Asymptotic Notation
Nine questions. The first five are notation facts; the rest make you count, name the case, handle an edge input, choose among named alternatives, and reason about the constant-factor crossover where asymptotics stop deciding. Click each question to reveal the answer — recompute before peeking.
1. What does O(f(n)) formally guarantee?
Answer: An asymptotic upper bound: there exist constants c > 0 and n₀ such that T(n) ≤ c·f(n) for all n ≥ n₀. It caps how fast the running time can grow, not how slow. It is not automatically “worst case” — that is which input you chose; O is how tightly you bound that cost function.
2. Is every O(n) algorithm also O(n²)?
Answer: Yes. Big-O is only an upper bound, and n² grows at least as fast as n, so anything bounded by n is also bounded by n². That is why O alone is not a “tight” description — reach for Θ when both sides hold.
3. What is the difference between Θ(n) and O(n)?
Answer: Θ (Theta) is a tight bound — the function grows at the same rate both from above and below. O is only the upper side. Θ(n) implies both O(n) and Ω(n). Example: linear search worst-case comparisons = n is Θ(n), not merely a loose O(n²).
4. Order these by growth, slowest to fastest: O(n²), O(1), O(2ⁿ), O(log n), O(n log n), O(n), O(n!).
Answer: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). Constant → logarithmic → linear → linearithmic → quadratic → exponential → factorial. (Bases of logs do not matter; bases of exponentials do: 3ⁿ is not O(2ⁿ).)
5. Simplify O(3n² + 5n + 100).
Answer: O(n²) (and in fact Θ(n²)). Drop constant coefficients and lower-order terms; as n → ∞ the n² term dominates everything else.
6. Count: nested pair scan. Code: for i from 0 to n-1: for j from i+1 to n-1: compare a[i], a[j]. How many comparisons for n = 6? What is the closed form and Big-O?
Answer: Comparisons = 5+4+3+2+1 = 15. Closed form: n(n-1)/2 = 6·5/2 = 15. Drop constants → Θ(n²) (or O(n²)). Fingerprint: double n roughly quadruples work. Edge: n = 0 or n = 1 → 0 comparisons, still O(1) work for the empty loops — the class for general n remains Θ(n²).
7. Case drill: linear search for target x in an unsorted array of n elements, stop when found. Give best, worst, and average (successful search, uniform position) as tight bounds. What if x is absent?
Answer: Best (x at index 0): Θ(1). Worst (x last): Θ(n). Average successful: (n+1)/2 comparisons → still Θ(n). If x is absent, every search does n comparisons → worst and “miss” average are Θ(n); there is no best-case early exit. Always name the case and the assumption (present vs absent).
8. Pattern / when-NOT: You need pairwise “any duplicate?” on n keys. Brute force is Θ(n²). Name two escape hatches, their complexities, and when you would not use each.
Answer: (1) Hash set of seen keys: O(n) time average, O(n) extra space; when-NOT: adversarial keys / need hard worst-case, or memory is tighter than time. (2) Sort then adjacent scan: O(n log n) time, O(1)–O(n) extra space depending on sort; when-NOT: you must not reorder (or must preserve original indices without an index array), or n is tiny and a double loop with better constants is simpler. Recognition signal for the quadratic baseline: nested loops over the same n (or O(n) work inside an O(n) loop).
9. Judgment / crossover: is an O(n log n) sort always faster than an O(n²) sort? Where does the answer flip, and how do real libraries exploit that?
Answer: No. Big-O drops the constant factor, and for small n the O(n²) algorithm with tiny constants wins. Insertion sort does about n²/4 comparisons on average but has almost no per-call overhead, no recursion, and streams the array in cache order; merge/quick sort pay call, partition, and allocation overhead on every subproblem. The crossover is typically around n ≈ 16–64. That is exactly why production sorts switch to insertion sort below a threshold: CPython’s Timsort uses a minrun of 32–64, and the C++ STL’s introsort (std::sort) drops to insertion sort for ranges of ≤ 16 elements. Lesson: asymptotic order decides the winner as n → ∞; below the crossover the measured constants decide, so profile at your real input sizes rather than trusting Big-O blindly. This is the one place “empirical timing beats asymptotic analysis” is literally true.
Self-check quiz authored for this guide — Grokking Algorithm Complexity & Big-O. Prefer Θ + named case + a one-line derivation in interviews.
🤖 Don't fully get this? Learn it with Claude
Stuck on Quiz? 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** (DSA) and want to truly understand it. Explain Quiz 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** 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** 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** 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.