Divide and conquer splits a problem into two independent halves, solves each by recursion, and combines the answers. The split is what gives the log depth.
About 3 min of reading
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Run a divide and recursion.
Sum by splitting.
Before you run it, say out loud what it will print. Then open the answer.
Max by splitting.
Before you run it, say out loud what it will print. Then open the answer.
Depth of halving 8.
Before you run it, say out loud what it will print. Then open the answer.
Max of one item.
Before you run it, say out loud what it will print. Then open the answer.
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
Halving gives log depth. Splitting off one item at a time gives linear depth. The split is the whole design choice.
If combining costs more than linear, the divide and conquer loses its speed. The merge in merge sort is kept linear on purpose.
def total(a):
if not a:
return 0
if len(a) == 1:
return a[0]
mid = len(a) // 2
return total(a[:mid]) + total(a[mid:])
print(total([1, 2, 3, 4]))Two halves summed on their own, then added. The work splits instead of stepping one at a time.
def big(a):
if len(a) == 1:
return a[0]
mid = len(a) // 2
left = big(a[:mid])
right = big(a[mid:])
return left if left > right else right
print(big([3, 9, 1, 7]))The bigger of the two half-maxes is the whole max. Two recursions, one combine.
def depth(n):
if n <= 1:
return 0
return 1 + depth(n // 2)
print(depth(8))Halving each call reaches one in three steps. The depth is the log, not the count.
def calls(n):
if n <= 1:
return 1
return 1 + calls(n // 2) * 0 + calls(n // 2)
print(calls(8))One call per node of the split tree. Halving keeps the count near n.
def total(a):
if not a:
return 0
if len(a) == 1:
return a[0]
mid = len(a) // 2
return total(a[:mid]) + total(a[mid:])
print(total([5, 5]))The combine is the plus. Change it and you change what the whole computes.
def big(a):
if len(a) == 1:
return a[0]
mid = len(a) // 2
left = big(a[:mid])
right = big(a[mid:])
return left if left > right else right
print(big([4]))A single item is both the max and the base. Splitting stops at one.
def total(a):
if not a:
return 0
if len(a) == 1:
return a[0]
mid = len(a) // 2
return total(a[:mid]) + total(a[mid:])
print(total([]))Guard the empty case before splitting. An empty split can loop.
def big(a):
if len(a) == 1:
return a[0]
mid = len(a) // 2
left = big(a[:mid])
right = big(a[mid:])
return left if left > right else right
print(big([2, 8]))Neither half needs the other until the combine. That independence is what makes it parallel-friendly.
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.