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
  1. How many recursive calls → .
  2. How much smaller the input is → (or “minus one”).
  3. 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 levelDominated byResult
grows downwardthe leaves
stays constantevery level equally
shrinks downwardthe 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Recursion