Let’s Divide and Conquer!
Programmers are constantly looking for ways to improve their code. Divide and conquer is one technique that allows them to approach problems in from a different perspective. The various algorithms show how algorithm design can have such a significant impact on complexity, speed, and efficiency of programs.
Divide and conquer is simply a strategy that divides a big problem into smaller subproblems, making it easier to solve them separately. This approach is used in various aspects of our life to deal with tasks more efficiently. The smaller sub-problems are recursively divided until they are solved.
The solved solutions are then merged to find a solution to the original problem. This article should help you get started with using this algorithmic approach to simplify and improve your code!
Before moving further, we need to first understand recursion.
When a function calls itself, it is referred to as recursion.
The function calls itself again and again until a certain point, at which it stops. The stopping point is called a base case or exit condition.
A base case is always added to a recursive function, otherwise, it would just be an endless loop!
The technique is divided into three steps:
1. Divide: If the problem is small, it can be solved directly. Otherwise, break the problem down into smaller subproblems. This step usually uses recursion to divide the problem until no further sub-problems are divisible.
2. Conquer: Conquer the smaller problems recursively until they’re solved. If the sub-problems are small enough, recursion is unnecessary, and they can be solved directly.
3. Combine: Combine the sub-problems to form a solution to the original problem.
WHY USE IT?
Divide and conquer algorithms are some of the fastest and easiest ways to optimize algorithms and make programs run faster. This simple technique allows us to decrease the time complexity of a program. To put it simply, the code you write takes much less time to execute and is thus useful in day-to-day programming.
Bubble Sort, for example, has a time complexity of O(n2), while quicksort has a time complexity of O(n log(n)). Linear Search has a time complexity of O(n), while Binary Search has a time complexity of O(log(n)).
WHERE IT CAN BE USED?
If our algorithm is slow and we want to speed it up, one of our first choices is divide and conquer. Whenever we encounter a problem that can be broken down into small pieces, we should check if it can be solved using this approach as it is easier to solve them.
So far, we’ve seen what the divide and conquer technique is. However, we need to understand how it works and what the code looks like.
Let’s look at a few applications that use the Divide and Conquer algorithm.
Merge Sort…
Merge Sort is a well-known sorting algorithm that uses the divide and conquer approach. The algorithm works like this:
- Divide the sequence of n numbers into 2 halves
- Recursively sort the two halves
- Merge the sorted halves into a single sorted sequence
Once you’ve determined how to break a problem down into several smaller pieces, you can execute these pieces at the same time. This reduces the time complexity of the algorithm, thereby making it faster.
If the size of the list is greater than 1, we divide the list and each sub-list by 2 until we get sub-lists of size 1. If the size is 1, the list is already sorted, so we don’t need to do anything. Instead of repeatedly defining new functions, we define a core function that depends on recursion.
The function would:
- Handle the base case.
2. Make Recursive calls to both the halves.
3. Combine the results obtained from the recursive calls.
The base case is reached when the length of the list/array is 1. To make a recursive call, divide the array/list into two parts and use the sort() function on both. Store the results in the left and right variables.
Worst Case Scenario: O(nlogn), Best Case Scenario: Ω(nlogn)
Binary Search…
It is yet another classic problem in which the divide and conquer algorithm is used. Binary search is a searching algorithm that compares the value of the input element in the array to the middle element.
If the values match, return the middle index. Otherwise, if x is less than the middle element, the algorithm goes to the left side of the middle element; or else, it goes to the right side of the middle element. It cuts the search range in half each time it tries to find the desired number.
However, the array must be sorted for binary search to work.
Worst Case Scenario: O(logn), Best Case Scenario: Ω(1)
Let’s look at one more algorithm to understand how divide and conquer works!!!
Quick Sort…
The algorithm selects a pivot element and rearranges the array elements so that all elements smaller than the selected pivot element move to the left side of the pivot and all elements larger than the pivot element move to the right side. Finally, the algorithm sorts the subarrays to the left and right of the pivot element recursively.
In practice, however, it outperforms merge sort and rarely exceeds its worst-case complexity.
Worst-case scenario: O(n2).
Divide and Conquer method is also used to solve a variety of other problems, including :
· Fast Exponentiation
· Strassen’s Algorithm
· Kasturba Algorithm
· Closest Pair of Points
· Cooley–Tukey Fast Fourier Transform (FFT)
Divide and Conquer (D & C) vs Dynamic Programming (DP)
Sometimes, divide and conquer strategy and dynamic programming are mixed up as both divide the given problem into subproblems and solve the subproblems. How can one decide which one of them to use for a given problem? That easy! When the same subproblems are not evaluated repeatedly, use Divide and Conquer. For instance, in Binary search, we never evaluate the same subproblems twice. Dynamic Programming, on the other hand, is preferred to calculate the nth Fibonacci number.
One more time…
A divide and conquer algorithm tries to break down a problem into as many small chunks as possible because small chunks are easier to solve. It accomplishes this by recursion.
1. Divide/ Break. Dividing the problem into smaller sub-problems.
2. Conquer /Solve: Solve the Sub-problems.
3. Combine /Merge: Merge the subproblems into a solution.
