Practice question · Multiple choice
Merge sort's cost recurrence is T(n) = 2T(n/2) + O(n). Which part of that expression produces the log n factor, and which produces the n?
Hints
- How many times can you halve n before reaching 1?
- At each level of the recursion, how much total merging happens across all the subproblems?
Show the answer
B. The halving gives log n levels, the merge gives the n
Why
Halving gives log n levels; merging touches every element once per level, giving O(n) each. Their product is the answer, and reading a recurrence this way, depth times work per level, is what the Master Theorem formalises and what lets you predict a design change before implementing it.
Practise Recurrence Relations
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.