Algorithms from zero
Thinking & complexity: multiple-choice review
Crux Multiple-choice synthesis across the complexity unit — dominant terms, Big-O classes, the time-space tradeoff, and reading constraints to pick an approach.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySix questions that cut across the whole unit. None of them is a definition to recite — each one is a decision you make when you size up an algorithm before you ever run it.
Goal
Confirm you can connect step-counting, Big-O, complexity classes, the time-space tradeoff, and input constraints into one judgement: given some code and some limits, what does this cost and is it fast enough?
Quiz
Completed
An algorithm performs exactly 5n + n²/2 + 1000 basic operations on input of size n. What is its Big-O, and why?
Heads-up Big-O drops constant multipliers. 1/2 does not change how the cost scales when n doubles, so O(n²/2) and O(n²) are the same class — we write the simplest form, O(n²).
Heads-up Lower-order terms are dropped, not summed into the notation. Once n is large, n² overwhelms n, so the n term is negligible and the answer is just O(n²).
Heads-up Big-O is about growth as n grows large, not the value at small n. The +1000 is a fixed cost that never grows, so it vanishes against n² for any sizeable input.
Quiz
Completed
A problem states n ≤ 1,000,000 with a 1-second limit. Your first idea is a nested-loop O(n²) scan. Read the constraint — what does it tell you before you write any code?
Heads-up No constant-factor tuning closes a 10,000× gap. When the constraint rules out a complexity class, you change the algorithm, not the constants.
Heads-up The input bound n primarily caps the time budget: ~10⁸ ops/sec × the time limit. n ≤ 10⁶ maps directly to 'O(n log n) or better required'.
Heads-up Polynomial is not automatically feasible. O(n²) is polynomial and still 10¹² ops here — far over budget. The bound picks a specific class, not just 'polynomial vs exponential'.
Quiz
Completed
To detect a duplicate you can use a nested loop (O(n²) time, O(1) space) or a hash set (O(n) time, O(n) space). On a server with memory to spare and users waiting on the response, which do you pick and why?
Heads-up Less memory is only better when memory is the binding constraint (embedded, mobile). Here memory is plentiful and latency matters, so trading memory for an O(n²)→O(n) speedup is the right call.
Heads-up They do not. The nested loop is O(n²); the hash set is O(n). For large n that is the difference between a trillion and a million operations.
Heads-up Backwards: the hash set uses MORE memory (O(n) vs O(1)). You pick it despite the extra memory because it buys a large time saving — that is the tradeoff.
Quiz
Completed
A function has a single loop that runs n times, and inside it calls binary search (O(log n)) on a sorted array. What is its time complexity?
Heads-up You add complexities only for sequential, independent phases. Here the search is INSIDE the loop, so it runs once per iteration — the costs multiply, giving O(n log n).
Heads-up log n is not constant; it grows with n (slowly). It cannot be dropped to O(1). Per-iteration O(log n) work across n iterations is O(n log n).
Heads-up Quadratic comes from a loop whose inner work is O(n), i.e. another full n-pass. Here the inner work is O(log n), not O(n), so it is O(n log n), well below O(n²).
Quiz
Completed
A junior writes largestOf with `let largest = 0` instead of `let largest = numbers[0]`, tests it on several positive-number lists, and ships it. What is the deeper lesson when it returns 0 for [-5, -3, -1]?
Heads-up Initialisation does not change the step count; the loop still runs n−1 times. This is a correctness bug, not a complexity one — it returns the wrong answer.
Heads-up All-negative lists are valid inputs the specification must cover. A loop-invariant argument catches the bug for every input class without needing to enumerate them as tests.
Heads-up Big-O measures growth of cost, not correctness. A wrong algorithm and a right one can share the same O(n). Correctness is proved with invariants and edge-case reasoning, not Big-O.
Quiz
Completed
Two sort routines are both 'correct'. Merge sort is O(n log n) time / O(n) space; bubble sort is O(n²) time / O(1) space. For sorting 1,000,000 records on a normal machine, what is the right read?
Heads-up At a million records bubble sort's 10¹² operations are hopelessly slow. The O(1) space saving is irrelevant when the time cost is 50,000× worse and memory is not the constraint.
Heads-up Both are correct, but correctness says nothing about cost. The O(n log n) vs O(n²) gap is the entire point — at scale only one finishes in reasonable time.
Heads-up O(n²) is practical only up to a few thousand elements. At 10⁶ it is ~10¹² operations — far past the feasible range, which is exactly why O(n log n) sorts exist.
Recap
The through-line of the unit is one habit: before you run anything, estimate the cost. Count steps, keep only the dominant term, name the Big-O class, weigh time against space for your real constraint, and let the input bound tell you which class is even allowed. And never confuse cost with correctness — Big-O measures how fast, a loop invariant proves whether it is right at all.