[Introduction] Divide and Conquer Algorithm

1. What is Divide and Conquer?

A divide and conquer algorithm is a strategy of solving a large problem by

1. breaking the problem into smaller sub-problems
2. solving the sub-problems, and
3. combining them to get the desired output.

To use the divide and conquer algorithm, recursion is used.

 

2. How Divide and Conquer Algorithms Work?

1. Divide : Divide the given problem into sub-problems using recursion
2. Conquer : Solve the smaller sub-problems recursively. If the subproblem is small enough, then solve it directly.
3. Combine : Combine the solutions of the sub-problems that ar part of the recursive process to solve the actual problem.

 

3. Example : Merge Sort

1. Let the given array be :

2. Divide the array into two halves.

Again, divide each subpart recursively into two halves until we get individual elements.

3. Combine the individual elements in a sorted manner.

4. Time Complexity

We will apply master theorem to calculate the complexity of the divide and conquer algorithms.

 

T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed to have the same size.
f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions

T(n) = aT(n/b) + f(n)
     = 2T(n/2) + O(n)
Where, 
a = 2 (each time, a problem is divided into 2 subproblems)
n/b = n/2 (size of each sub problem is half of the input)
f(n) = time taken to divide the problem and merging the subproblems
T(n/2) = O(n log n) (To understand this, please refer to the master theorem.)

Now, T(n) = 2T(n log n) + O(n)
          ≈ O(n log n)

 

5. Divide and Conquer vs Dynamic Approach

The divide and conquer approach divides a problem into smaller subproblems; these subproblems are further solved recursively. The result of each subproblem is not stored for future reference, whereas, in a dynamic approach, the result of each subproblem is stored for future reference.

 

Use the divide and conquer approach when the same subproblem is not solved multiple times. Use the dynamic approach when the result of a subproblem is to be used multiple times in the future.

 

# Divide and Conquer 
def fib(n): 
    if n < 2 : 
    	return 1
    else : 
    	return f(n - 1) + f(n -2)
        
# Dynamic Approach 
mem = []
fib(n)
    If n in mem: return mem[n] 
    else,     
        If n < 2, f = 1
        else , f = f(n - 1) + f(n -2)
        mem[n] = f
        return f