Micro-questions over the recurrences module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The cost that refers to itself
1. Ask “how long does merge sort take on elements?” — what is the answer?
Answer
However long it takes on elements, twice, plus for the merge. The answer is written in terms of the question.
2. Write that as a recurrence.
Answer
3. What is a recurrence relation?
Answer
An equation defining a function’s value at using its values at smaller inputs, together with a base case.
4. What does “solving” one mean?
Answer
Finding a closed form — an expression for with no on the right-hand side — or at least its growth rate.
B. The vocabulary
5. What is the branching factor ?
Answer
How many recursive calls one call makes. Merge sort ; binary search ; naive Fibonacci .
6. What is the shrink factor ?
Answer
The factor by which the input gets smaller when the shrinking is divisive. Merge sort has . A recursion that shrinks by subtraction has no at all.
7. What is ?
Answer
The combine work (or driving function) — the non-recursive work one call does, everything outside the recursive calls. For merge sort it is the merge, .
8. In a recursion tree, what is each node labelled with?
Answer
The work that node alone does, excluding its children.
9. What is the depth of a divisive recurrence? A subtractive one?
Answer
for divisive; (or ) for subtractive.
10. How many leaves does a divisive recurrence have?
Answer
.
11. What is the substitution method?
Answer
Guessing a closed form and proving it correct by induction. It is the rigorous companion to the recursion tree, which is really a way of finding the guess.
C. From code to recurrence
12. What three things do you read off the code?
Answer
- How many recursive calls → .
- How much smaller the input is → (or “minus one”).
- How much work outside the recursive calls → .
Then .
13. Give the recurrence for binary search, merge sort, and naive Fibonacci.
Answer
Binary search: .
Merge sort: .
Naive Fibonacci: .
14. What is the mistake to avoid at this step?
Answer
Counting the recursive work twice. is only what the current call does itself — in merge sort the merge, never the sorting of the halves, which the term already covers.
15. Why is tree traversal not honestly ?
Answer
That assumes a balanced tree. An unbalanced one is — which is why traversal is argued by “each node is visited once” rather than by this machinery.
D. The recursion tree
16. What is the key move that makes the tree method work?
Answer
Sum across each level rather than down each branch.
17. For , what is the work at level ?
Answer
nodes each of size doing work — level total , regardless of .
18. Finish the derivation.
Answer
levels, each doing , so . At : 7 levels × 64 = 448.
19. Give the general level arithmetic.
Answer
20. What are the only three things that quantity can do, and what does each give?
Answer
| Work per level | Dominated by | Result |
|---|---|---|
| grows downward | the leaves | |
| stays constant | every level equally | |
| shrinks downward | the root |
21. What is that table?
Answer
The entire content of the Master Theorem, derived. The theorem is this table with the conditions made precise.
22. Why is “dominated by” legitimate?
Answer
Because these are geometric series. If work shrinks by a factor , the total is — a constant multiple of the root. If it grows by , the last level is a constant fraction of the whole sum.
23. For at , what do the level totals do?
Answer
— halving. Total 8,128, under . The root alone accounts for half the entire tree.
24. And for ?
Answer
— doubling. Total 127, and the bottom level alone is more than half.
E. Worked case
25. For , what is the level work?
Answer
— multiplied by each step, so it grows downward.
26. So what dominates, and what is the complexity?
Answer
The leaves. There are of them, so .
27. What is the doubling test?
Answer
If you think an algorithm is , double the input and see whether the time multiplies by . Linear doubles, quadratic quadruples, does slightly more than double, barely moves.
28. Why is it the most useful practical skill here?
Answer
You can check a complexity claim in two runs without reading a line of the implementation.
29. What does the doubling test predict for , and what was measured?
Answer
, and the measurements converge on 3.06, 3.04, 3.03, 3.02.
F. The catalogue
30. Give the solutions for the four subtractive recurrences.
Answer
; ; .
31. Give the solutions for the divisive ones.
Answer
; ; ; ; ; ; .
32. Compare with — what is the lesson?
Answer
Same branching, same shrinking; only versus combine work — and that alone is versus . Merge sort cannot be made linear by clever coding: a linear combine at every level is where the comes from.
33. Compare with — what is the lesson?
Answer
Subtracting one gives levels; dividing by two gives . Shrinking multiplicatively rather than additively is the single highest-leverage move in algorithm design — it is why binary search, balanced trees and divide-and-conquer all exist.
34. What is the lesson of ?
Answer
Branching with subtractive shrinking is always exponential. This is naive Fibonacci — and why memoisation there is not an optimisation but a change of algorithm.
G. Substitution
35. Prove is by substitution.
Answer
Guess . Then
which is whenever .
36. Which step do people get wrong?
Answer
Assuming the bound for without checking the leftover terms cancel in the right direction. Here is what pinned down . If the leftovers went the other way, the guess needs strengthening — typically to .
H. Traps
37. Is the base of the logarithm irrelevant?
Answer
Inside , yes — logs differ by a constant factor. In the level arithmetic, no: the depth really is , which is what tells you a 3-way split has depth .
38. Is more branching always worse?
Answer
No. is ; Strassen’s is — one fewer subcall changes the exponent. Branching interacts with shrinking; neither alone decides.
39. What does drawing a balanced tree silently assume?
Answer
The thing you may need to prove. Quicksort is ; balanced splits give and gives .
40. For , what happens if you only count internal nodes?
Answer
You conclude and are badly wrong. The leaves are the whole cost — there are of them each doing constant work.
41. Summarise the method in one sentence.
Answer
Read , and off the code, compute the work per level, and ask whether it grows, stays flat, or shrinks — the answer is the leaves, every level, or the root.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Recursion Trees & Recurrences — the module
- The Master Theorem — Question Bank — this table made precise
- Recursion Fundamentals — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering