Micro-questions over the growth and asymptotics module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why growth rate
1. Method A takes 2.5s on a gaming laptop, Method B takes 5.0s on a cheap server. Is A the better algorithm?
Answer
Not necessarily. Runtime in seconds depends on hardware speed, language overhead and CPU load — none of which are properties of the algorithm.
2. What does computer science measure instead?
Answer
How the workload grows as input size scales to infinity.
3. At , contrast with .
Answer
takes about 11 days; finishes in 0.2 seconds — on the exact same computer.
4. Why is that comparison the whole argument for the subject?
Answer
Because no hardware upgrade closes an 11-days-to-0.2-seconds gap. Growth rate beats constant factors at scale, always.
B. The three asymptotics
5. What does mean, formally and plainly?
Answer
Formally . Plainly: an upper bound — at worst, work grows no faster than .
6. What does mean?
Answer
— a lower bound. At best, work grows no slower than .
7. What does mean?
Answer
— a tight bound. Work grows exactly like .
8. State the tight bound rule.
Answer
holds if and only if both and hold simultaneously.
9. Is it correct to say bubble sort is ?
Answer
Technically yes — Big-O is an upper bound and . It is just useless. This is why exists: it forbids a loose claim.
C. Cases versus bounds
10. What are best, average and worst case?
Answer
Best: the input needing the minimum operations. Average: expected work over all probable inputs. Worst: the input causing maximum work.
11. What is the relationship between the three cases and the three notations?
Answer
They are independent. , and are mathematical bounds on a function; best/average/worst choose which function you are bounding. You can state a for the best case.
12. Give the search example for best and worst case.
Answer
Searching for an item at index 0 is (best); searching for a missing item is (worst).
13. Why is worst case the production standard?
Answer
Because attackers choose the input. A hash map is average and worst case, and hash-flooding denial of service deliberately triggers the gap.
D. Recurrences
14. Give the merge sort recurrence and solve it by tree.
Answer
. Tree height , work per level , total .
15. Give the binary search recurrence and solve it.
Answer
. Height , work per level , total .
16. What is the structural difference between those two?
Answer
Merge sort recurses into both halves; binary search discards one. Same height, completely different total.
E. Amortised analysis
17. What does amortised analysis measure?
Answer
The average cost per operation across a guaranteed sequence of operations, where rare expensive steps are paid for by many cheap ones.
18. Walk through the dynamic array append example.
Answer
Normal push ; resize push . Because capacity doubles, appending items totals copies, so
19. How does amortised differ from average case?
Answer
Average case is a statement about the distribution of inputs; amortised is a guarantee about a sequence regardless of input. Amortised does not assume anything is random.
F. Reading constraints
20. Give the constraint → complexity table.
Answer
| Allowed | Family | |
|---|---|---|
| 12 | permutations, backtracking | |
| 25 | subsets, bitmask DP | |
| 500 | Floyd–Warshall, triple loops | |
| 10,000 | quadratic sorts, double loops | |
| 1,000,000 | / | merge sort, hash maps, two pointers |
| / | binary search, math, bitwise |
21. What is this table actually for?
Answer
Reading the intended solution off the constraints before you start — in interviews and competitive programming, is a near-explicit instruction to enumerate subsets.
G. Space complexity
22. Distinguish total space from auxiliary space.
Answer
Total includes the input arrays. Auxiliary is the extra temporary memory the algorithm allocates, excluding the input.
23. What is an in-place algorithm?
Answer
One with auxiliary space — it modifies data directly inside the input array.
24. What is the hidden call stack trap?
Answer
Recursive functions consume auxiliary memory proportional to recursion depth . A recursive function that allocates nothing still takes space.
25. Is a recursive in-order traversal in-place?
Answer
No — it uses call stack, which is balanced and degenerate. Only an iterative Morris traversal is genuinely .
H. Traps
26. Simplify .
Answer
— completely dominates for large inputs.
27. An algorithm processes an array of length and a string of length . What is the complexity?
Answer
— not . Different variables must stay different.
28. When does an algorithm beat an one?
Answer
At small inputs — around , insertion sort beats quicksort on constant overhead. This is why real sort implementations switch to insertion sort for small subarrays.
29. Summarise the module in one sentence.
Answer
Measure growth rather than seconds, bound it above (), below () or tightly (), design against the worst case, and read the constraints to know which family is expected.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Growth & Asymptotic Notation — the module
- Amortized Analysis — Question Bank — the next bank
- Dynamic Arrays — Question Bank — the worked amortised example
Software engineering
Infrastructure & security
Computer science
Hardware & engineering