Divide and Conquer
Split the input, solve the parts recursively, combine the results.
Recursion Trees: Divide and conquer over a range
Range 0-7 has 8 elements. Split at 3: recurse on 0-3, then on 4-7, and combine afterwards. Depth 0.
Cost
- Space
- O(log n)
Cost given by the recurrence. See Master Theorem.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Recursion Trees covers these too, in the same run.