AlgoScope

Divide and Conquer

Split the input, solve the parts recursively, combine the results.

Divide and conquer, technique, intermediate
Split 0 to 7 at 3.0-7call
Split 0 to 7 at 3.0-7call

Recursion Trees: Divide and conquer over a range

Decision, step 2 of 32

Range 0-7 has 8 elements. Split at 3: recurse on 0-3, then on 4-7, and combine afterwards. Depth 0.

How recursion trees works

Cost

Space
O(log n)

Cost given by the recurrence. See Master Theorem.

Leads to

Topics that need this one first.

Taught by the same lesson

Recursion Trees covers these too, in the same run.