Unit 2: Divide & Conquer
Divide and Conquer Strategy
12 min read · 80% complete
Explanation
Break the problem into smaller pieces, solve each piece, then join the answers together.
Merge sort is the classic example: split the list in half, sort both halves, merge them.
Key exam points
- Divide, conquer, combine
- Merge sort is stable; quick sort is in-place
- Strassen: O(n^2.81)
Previous year questions
Write the merge sort algorithm and derive its time complexity.
2023 · 10 marks
Practice quiz
Worst case of quick sort is: