Divide and Conquer

Divide and Conquer

The divide-and-conquer design paradigm

1. Divide the problem (instance) into subproblems.
2. Conquer the subproblems by solving them recursively.
3. Combine subproblem solutions.

EXAMPLE:

1. Merge sort \(T(n)=2T(n/2)+\Theta(n)\Rightarrow T(n)=\Theta(n\lg n)\)​

2. Binary search \(T(n)=T(n/2)+\Theta(1)\Rightarrow T(n)=\Theta(\lg n)\)

3. Powering a number \(T(n)=T(n/2)+\Theta(1)\Rightarrow T(n)=\Theta(\lg n)\)

Read more »