Skip to content

Latest commit

 

History

History
15 lines (12 loc) · 672 Bytes

divide_and_conquer.md

File metadata and controls

15 lines (12 loc) · 672 Bytes

Divide and Conquer

Divide and conquer is "an algorithm design paradigm that is based on multi-branch recursion. It takes a larger problem and breaks it into 2+ sub-problems" (Wikipedia). Merge sorting and some fibonacci algorithms are implementations of the divide and conquer algorithm. These are especially useful on multi-processor systems.

Code Example

def multiply_range(n, m):
	if n == m:
		return m
	if m < n:
		return 1
	else:
		return multiply_range(n, (m+n)/2) * multiply_range((n+m)/2 + 1, m)