• Author / Uploaded
• Abhishek Nandy

Citation preview

Divide and Conquer Like dynamic and greedy methods, Divide and Conquer is an algorithmic paradigm. A typical Divide and Conquer algorithm solves a problem using following three steps. 1. Divide problem into several smaller sub problems o Normally, the sub problems are similar to the original 2. Conquer the sub problems by solving them recursively o Base case: solve small enough problems by brute force 3. Combine the solutions to get a solution to the sub problems o And finally a solution to the original problem 4. Divide and Conquer algorithms are normally recursive. The following algorithms are based on divide-and-conquer algorithm design paradigm − 

Merge Sort



Quick Sort



Binary Search

Binary search 15

27

33

83

92

99

Search=99, low=0, high=5, mid= (low + high)/2=0+5=2 Pass 1 15

27

33 83 | Check for 99

92

99

Search=99, low=2+1=3, high=5, mid= (low + high)/2=3+5=4 Pass 2 15

27

33

83

92 99 | Check for 99

Search=99, low=5, high=5, mid= (low + high)/2=5+5=5

Pass 3

15

27

33

83

92

99 | finds 99

Pseudo code for binary search Binary Search (arr[],l, r, x) { If (r >= l) { mid = ( l + r ) / 2;

If (arr[mid] == x) Return mid; If (arr[mid] > x) Return Binary Search (arr, l, mid - 1, x); Return binarySearch(arr, mid + 1, r, x); }

Return -1; }

Complexity of binary search The recurrence relation for Binary search can be given as T (n) = 1

for n2 Let say the iteration in Binary Search terminates after k iterations. In the above example, it terminates after 3 iterations, so here k = 3 At each iteration, the array is divided by half. So let’s say the length of array at any iteration is n. At Iteration 1, Length of array = n At Iteration 2, Length of array = n⁄2 At Iteration 3, Length of array = (n⁄2)⁄2 = n⁄22 Therefore, after Iteration k, Length of array = n⁄2k

Also, we know that after After k divisions, the length of array becomes 1 Therefore Length of array = n⁄2k = 1 => n = 2k Applying log function on both sides: => log2 (n) = log2 (2k) => log2 (n) = k log2 (2) As (loga (a) = 1) Therefore, => k = log2 (n) Hence the time complexzity of Binary Search is log2 (n)

Merge sort

Let's consider an array with values {14, 7, 3, 12, 9, 11, 6, and 12} Below, we have a pictorial representation of how merge sort will sort the given array.

In merge sort we follow the following steps: 1. We take a variable p and store the starting index of our array in this. And we take another variable r and store the last index of array in it. 2. Then we find the middle of the array using the formula (p + r)/2 and mark the middle index as q, and break the array into two subarrays, from p to q and from q + 1 to r index. 3. Then we divide these 2 subarrays again, just like we divided our main array and this continues. 4. Once we have divided the main array into subarrays with single elements, then we start merging the subarrays.

Pseudo code for merge sort

I/P: Unsorted array of size n O/P: sorted array of size n Mergesort (A, low, high) { If (low