Divide and Conquer
Split the input, solve the parts recursively, combine the results.
Decision · step 2 of 32Recursion 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.
What you will see
SPLIT -> RECURSE -> COMBINE as a tree of ranges.
Cost
| Space | O(log n) |
|---|
Cost given by the recurrence; see Master Theorem.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input.
Screen readers: Each call frame announces its range and result; each step announces split, recurse or combine.
Reduced motion: Frames appear and disappear with crossfades; ranges highlight without motion.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Recursion Trees covers these too, in the same run.