Introduction to the Divide and Conquer Algorithm

Let’s understand with an example.

Assume you have an integer array of some length, and your big task is to sort the array in ascending order.

Let us assume that the Time Complexity is your power and you have limited power such that you cannot use other brute-force approaches like Bubble Sort, Insertion Sort, or Selection Sort, which has a time complexity of O(n²).

What we can do here is that we can use a Divide and Conquer approach to solve the big problem that is to sort the array. The idea here is to divide the array into sub-arrays, sort the sub-arrays and merge them to get the sorted array.

Suppose this is our array,

 

9

8

3

7

5

4

 

According to the Divide and Conquer algorithm, we’ll first divide the array into smaller sub-arrays.

9 8 3

7 5 4

 

 

 

 

 

 

 

Now, we’ll further divide these into sub-arrays till we get a single element in each array.

9 8

3

7 5

4

 

9

8

3

7

5

4

 

 

 

 

 

 

 

 

 

 

 

 

Since there is only one element in each of our arrays, we’ll consider all the arrays as sorted arrays. Now our subproblem is solved because we have sorted all our smaller arrays.

 

The next step in divide and conquer is to combine the smaller results to solve the big problem. So here, we’ll start combining the smaller arrays to get a sorted resultant merged array.

9

8

3

7

5

4

 

8 9

5 7

 

3 8 9

4 5 7

 

3

4

5

7

8

9

 

Hence, merging all the results of the subtasks at all levels is the sorted array which is the result of the big problem.

 

The power used here or the time complexity of this algorithm is O(n * logn) which is significantly less than the brute force approaches O(n²).

 

The above method used to sort the array is known as Merge Sort in data structures. Merge Sort reduces the time complexity of the sorting function to a greater extent; hence it is used in most programs and projects.

 

Applications of the DAC Algorithm

There are many algorithms in data structures that use the divide and conquer approach. One of these is Merge Sort which we discussed above.

• Binary Search: The Binary Search algorithm searches an element in a sorted array in O(logn) time complexity.

In the Binary Search algorithm, we divide the array into two parts (left and right) based on the median of the array. We compare the median with our element, and if the median is greater than the element, we search in the left part, and if it is less than the element, we search in the right part of the array. We change the median accordingly and continue searching till the median is equal to the element.

 

• Quick Sort: Quick Sort algorithm is a very famous algorithm used to sort an array. Similar to the merge sort, quick sort also uses divide and conquer to sort the array.

In Quick Sort, we fix a pivot element and move all smaller elements to the left of the pivot and all larger elements to the right of the pivot element. Then we call recursion on the leftover left and right parts of the array.
 

• Strassen’s Algorithm: This algorithm is named after the German mathematician Volker Strassen. It is used for the task of matrix multiplication. In cases of large matrices, the computation cost required is very high by traditional methods; hence, this algorithm increases efficiency.

 

• Karatsuba Algorithm: This algorithm speeds up the multiplication process by using a divide and conquer approach. The usual binary multiplication takes O(n²) time, whereas this algorithm takes only O(n^1.59) time.

 

• Closest Pair of Points: This algorithm uses the DAC approach to find the closest pair (least distance) points from a set of points in a 2-D graph.

The Brute-Force solution for this problem will take O(n²) time because we’ll have to calculate all distances among all points and then select the minimum distance, but using Divide and Conquer, we can solve this task in O(n * logn) time complexity.

Also see, Euclid GCD Algorithm

What are the advantages of the DAC algorithm?

One of the most significant advantages of the DAC algorithm is that it significantly reduces the time complexity of a big problem by dividing it into smaller tasks. For example, to multiply two matrices using the traditional method requires O(n3) time but using DAC (or Strassen algorithm), we can bring it down to O(n2.8074).

The DAC algorithm can also be used to solve puzzles like the Tower of Hanoi; at first sight, it is challenging to attempt a complex puzzle but dividing it into smaller parts makes it easier to come up with a solution.

The DAC algorithm is ideal for multi-processing systems because it inhibits parallelism. It is also fast because it makes excellent use of cache memory without shifting too much computation to main memory, which is relatively slower.

Also Read - Selection Sort in C

Frequently Asked Questions

What are the Divide and Conquer algorithm?

Answer: The Divide and Conquer algorithm (or DAC) solves a very big task or a problem by breaking it into smaller sub-tasks or sub-problems; after solving, we combine all the sub-tasks in a specific manner so that we get the result for the big task.

What are the time complexities of various sorting algorithms?

Answer: The worst-case time complexities of various sorting algorithms are:

• Bubble Sort: O(n²)
• Selection Sort: O(n²)
• Insertion Sort: O(n²)
• Merge Sort: O(n * logn)
• Quick Sort: O(n * logn)
• Heap Sort: O(n * logn)

What are the applications of the divide and conquer algorithm?

Answer: Many applications of DAC are there in data structures:

1. Binary Search algorithm
2. Merge Sort
3. Quick Sort
4. Strassen’s Algorithm
5. Karatsuba Algorithm
6. Closest Pair of Points

Difference between Divide and Conquer and Dynamic Programming (DP).

Answer: The DAC algorithm and DP (or Memoization) use the principle of dividing a big task into smaller sub-tasks. But the major difference between these two is that the DP algorithm saves the result of the sub-problems to be utilized in the future, but in the case of DAC, the sub-tasks are further solved recursively and are not saved for future reference.

What are the disadvantages of the divide and conquer algorithm?

Answer: Some disadvantages of the Divide and conquer algorithm are:

• Most of the algorithms that use the DAC approach are implemented using recursion, making them costly in memory management.
• Stack space for recursive calling increases the space complexity.
• The DAC approach is challenging to implement when the sub-problems are not similar.

Key Takeaways

Kudos to you!! You already won if you are reading blogs in the world of toxic social media and Instagram reels.

Divide and Conquer is a very crucial algorithm in Data Structures and Algorithms. In this blog, we saw its origin, application, and advantages. From the interview point of view, this blog is a must-read so bookmark it for future reference.

Recommended Problem - K Closest Points To Origin

Also, if you are preparing for the upcoming Campus Placements, then don’t worry. Coding Ninjas has your back. Visit this link for a carefully crafted and designed course on-campus placements and interview preparation.