Data structures and algorithms
What does the recurrence T(n) = 2T(n/2)+O(n) solve to?
AppliedMultiple choiceFree solution
What does the recurrence solve to?
- A
- B
- C
- D
Try it
Pick an answer
Show the answer and worked solution
Answer: B –
Draw the recursion tree. Each level does work in total and there are levels, so the answer is . In master-theorem terms this is the tied case, with and . It is merge sort, and recognising it on sight is worth more than re-deriving it. Changing to 3 would tip it into the leaf-dominated case and give , so the comparison between and is the whole test.
Worked solution
- Formula
- Substitute
- SolveThe tied case.
- One extra subproblem changes the class.
- Answer
Sanity check. Each of the levels does work in total, which is the recursion tree drawn in one line.
- A. The linear work happens at every one of levels.
- B. Correct – , so the tied case applies. This is merge sort.
- C. That would need the work outside the calls to be quadratic.
- D. That is the binary-search recurrence, with one subproblem and constant work.
Takeaway: Recognise on sight.
Report an issue with this question
Learn the method
Of the kind reported at
More data structures and algorithms questions
- You need the 100 largest values from a stream of 10⁹ numbers you cannot store.Foundation · Free solution
- Climbing a staircase, part 3 of 3Advanced · Premium
- How many times does the inner body run in for i in range(1000): for j in range(i): body()?Foundation · Premium
- A hot-path buffer is a dynamic array with O(1) amortised push.Applied · Premium
- What does the recurrence T(n) = 4T(n/2)+Θ(n²) solve to?Applied · Premium
- A dynamic array starts with capacity 1 and doubles when full, copying all elements.Applied · Premium