Divide And Conquer Approach

In the present world, software companies are recruiting people who are developing the code, the time complexity of the code should be minimal. Beginners are using the brute force method or the naïve method to develop the code, which gives the maximum time complexity and the code will be complex. To get recruited we need to develop the most efficient code as well as the time complexity of the code should be minimum.

At present we would be thinking about how can we minimize the time complexity of our code?

One of the best techniques is “Divide and Conquer”, using this technique we can get efficient code and minimize the time complexity of the code.

Divide and Conquer Approach

The divide and conquer technique works by dividing the problem recursively into the subproblems until it is solved directly and finally it combines the solution of all the subproblems to get the solution of the original problem. The actual idea behind the divide and conquer algorithm is it is easy to deal with small problems one by one instead of dealing with the large problem all at once. This method reduces the time complexity to a large extent.

Phases of Divide and Conquer Approach

The Divide and Conquer are divided into three phases:

Divide: Dividing the problem into two or more sub-problems that are similar to the original problem but smaller in size.

Conquer: Solving the sub-problems recursively.

Combine: Combine all the solutions of the sub-problems to get the solution to the original problem.

Let us discuss more, how the divide and conquer technique can minimize the time complexity of the code. I will compare algorithm that uses the divide and conquer technique with the brute force or the basic algorithms, so it will be very helpful to understand the topic.

Binary Search Algorithm

Searching for a number in an array and if the number exist then return the index or else return “number is not in the array”.

If we use a naïve method such as a linear search, the search element is compared to all the elements in an array till the element is found or till the end of the array. The time complexity of the code in the worst situation is O(n).

Binary Search is not the best algorithm, but it is the simplest and basic algorithm of the divide and conquer technique. In this, we use only two phases out of three phases that are divide, conquer but not combine. When we use Binary sort it actually divides the array into sub-arrays. It compares the searching element with the middle element if it is less than the middle element then it divides the left part of the array into a sub-array or else it divides the right part into a sub-array and this process recursively takes place till it gets the search element or till the end of the array. The time complexity of the code is O(log(n)).

The Binary search is very useful than the naïve method as we do the work in a smaller number of comparisons and we also know that O(log(n)) is less than O(n). The disadvantage of binary search is the array should be sorted.

The detailed steps of binary search are:

Step 1: Compare the search element with the middle element of the array.

Step 2: If the search element and middle element of the array are the same then return the value.

Step 3: If the search element is greater than the middle element then use the right sub-array and use recursive calls.

Step 4: If the search element is lesser than the middle element then use the left sub-array and use recursive calls.

The recurrence relation of binary search is: T(n) = T(n/2) + 1

Merge Sort Algorithm

Sorting is a process of arranging all the elements of an array in an ordered manner that is in ascending or descending manner.

If we use the naïve method such as bubble sort, we compare the adjacent elements and check whether the element is sorted or not. To complete all the comparisons the time complexity of the bubble sort is O(n²).

Merge Sort is an algorithm of divide and conquer. In merge sort, we use all three phases. In merge sort, we actually divide the original array into the sub-arrays recursively, each sub-array is sorted and finally, we combine the sorted sub-arrays and get the original sorted array. The time complexity of the code is O(n log(n)).

The merge sort can be done with fewer comparisons compared to the naïve method and we also know that O (n log(n)) is less than O(n²), which has minimized the time complexity. Now we can understand it is better to use Merge Sort instead of the naïve methods when we deal with complex problems so we can minimize the time complexity of the code.

The detailed steps of merge sort are:

Step 1: Compare the middle point to divide the array into two halves.

Step 2: Recursively call the function for the first half.

Step 3: Recursively call the function for the second half.

Step 4: Merge everything that we have obtained from step 2 and step 3 and finally, we will get a sorted array.

The recurrence relation of merge sort is: T(n)=2T(n/2) + n

Applications of the Divide and Conquer Technique

Some algorithms which use the divide and conquer approach are:

Closest Pair Problem — This algorithm is used to compute the closest distance between a pair of points in space. The time complexity of the algorithm using the divide and conquer approach is O(n log(n)) and using the naive approach is O(n²).

Strassen’s Algorithm — This algorithm is used for performing matrix multiplication and it is named after Volker Strassen. The time complexity of the algorithm using the divide and conquer approach is O(n^(2.81)) and using the naive approach is O(n³).

Karatsuba Algorithm — This algorithm is used to multiply two n-digit numbers and it reduces it to at most single digits. The time complexity of the algorithm using the divide and conquer approach is O(n^(1.59)).

Cooley-Tukey Fast Fourier Transform(FFT) Algorithm — This algorithm is named after J. W. Cooley and John Tukey. This algorithm is used to compute the discrete Fourier transform of a sequence or its inverse. The time complexity of the algorithm using the divide and conquer approach is O(n log(n)).

Advantages of Divide and Conquer Approach

· It helps to solve difficult and complex problems easily such as the Tower of Hanoi.

· With the help of the divide and conquer technique we can design an efficient code.

· It efficiently uses cache memory.

· It is more proficient than brute force technique.

· If we use floating numbers, then the results may improve since round-off control is very efficient in such algorithms.

Disadvantages of the Divide and Conquer Approach

· Recursion is slow.

· Use of explicit stacks may use extra space.

· It may be more complex than the basic iterative approach.

· The sub-problems can occur repeatedly which increases the solving time and extra space is needed. Saving the solution to the repeated sub-problem is called Memorization.

· The system may crash if the recursion performed is greater than the stack present in the CPU.

Summary

· Practicing algorithms using this approach helps to improve recursive problem-solving skills.

· The important part of this approach is the base case, every recursive algorithm needs a base case and it should be correct.

· This approach can also be implemented by a non-recursive algorithm. In this case, we need to store the solution of smaller subproblems in an explicit stack data structure.