Example: merge sort 1 Divide: trivial 2. Conquer. recursively sort 2 subarrays 3. Combine: Linear-time merge 7(n)=2(m2)+O(m) subproblems work dividing and combining subproblem size Day 4 Introduction to Algorithms L3.3Day 4 Introduction to Algorithms L3.3 Example: merge sort 1. Divide: Trivial. 2. Conquer: Recursively sort 2 subarrays. 3. Combine: Linear-time merge. T(n) = 2 T(n/2) + O(n) # subproblems subproblem size work dividing and combining