COMPSCI320 Chap.6 Divide and Conquer Recurrences and Inversions
Divide and Conquer Recurrences and Inversions
Divide and conquer was the largest midterm topic, so this chapter covers its analysis carefully. It shows how to read a recurrence from code, how a recursion tree reveals the solution, how to apply the Master theorem by naming a, b and c, and how to prove an exact formula by induction.
It then counts inversions while merging, the standard O(n log n) example.
The examples follow the marking pattern of the midterm divide and conquer question: name the recurrence, quote the theorem with its conditions, apply it with the constants and prove an exact formula on powers of two. The binary-search drills connect the theory to the third programming assignment.
What this chapter covers
- 01
Writing a recurrence from pseudocode
- 02
Recursion trees and level costs
- 03
The three cases of the Master theorem
- 04
Induction proofs for halving recurrences
- 05
Counting inversions while merging
- 06
Binary search on sorted and rotated arrays
Worked example · free
Count cross inversions during a merge
- 1Output 2; then 3 is smaller than 5, 7 and 11, adding 3 inversions.
- 1Output 4 before the same three values, adding 3 more.
- 1Output 5 and 7; then 8 and 9 are each smaller than 11, adding 1 each.
- 1The cross count is 3 + 3 + 1 + 1 = 8, matching a check of all pairs.
Key terms
- Recurrence
- An equation that expresses the running time on an input of size n through running times on smaller inputs.
- Master Theorem
- A rule that solves T(n) = aT(n/b) + Θ(n^c) by comparing c with the logarithm of a to base b.
- Recursion Tree
- A diagram of the subproblems of a recursive algorithm, level by level, used to add up their costs.
- Inversion
- A pair of positions in a sequence whose values appear in the opposite order to sorted order.
- Combining Work
- The cost a divide and conquer algorithm spends outside its recursive calls, such as a linear merge.
- Sort and Count
- A divide and conquer algorithm that returns both a sorted list and its number of inversions.
Divide and Conquer Recurrences and Inversions FAQ
Which constants must I state when applying the Master theorem?
Name a, the number of recursive calls, b, the factor by which the input shrinks, and c, the exponent of the combining work. Then compute the logarithm of a to base b, say which of the three cases holds and give the Theta class. Mergesort, with a = 2, b = 2 and c = 1, falls in the middle case and gives n log n.
What if a recurrence does not fit the Master theorem?
Recurrences that shrink by subtraction, such as T(n) = T(n − 1) + n, or that have uneven pieces need another method. Unroll a few levels to spot the pattern, write the sum, and then prove the closed form by induction. The 2026 midterm asked for exactly such an induction on a halving recurrence.
Why does counting inversions take only n log n time?
Inversions inside each half are counted recursively, and inversions between the halves are counted during the merge. Because both halves are sorted, one comparison tells you how many waiting values form inversions with the element being output, so the merge stays linear. The recurrence is the mergesort recurrence.
Why do induction proofs on recurrences use powers of two?
On powers of two every halving is exact, so the recurrence has no floors or ceilings and the algebra stays clean. The 2026 answer key states its claim for all powers of two before proving it. The asymptotic class for other input sizes then follows from monotonicity, which is usually not required in the written answer.
Exam move
Collect six recurrences, two for each case of the Master theorem, and solve them naming a, b and c each time. Prove one halving recurrence by induction with the four labelled parts. Then run sort and count on a short sequence by hand and check the total against a list of all pairs. In the last week, mix recurrences from this chapter with those of Chapter 7 so that recognising the case of the Master theorem becomes automatic.
When a recurrence surprises you, sketch its recursion tree for three levels to see which part dominates.
Working through Divide and Conquer Recurrences and Inversions in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Divide and Conquer Recurrences and Inversions question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
