Divide and Conquer Algorithm

What exactly is an algorithm?

An algorithm is a step-by-step procedure that specifies a sequence of instructions that must be followed in a certain order in order to obtain the desired outcome.

There are several different types of algorithms, but this article will focus on the most important and basic algorithm which is Divide and Conquer Algorithm.

An algorithm is a finite sequence of well-defined, computer-implementable instructions for solving a class of problems or conducting a computation. An algorithm is a function that can be represented in a formal language that can be evaluated in a finite amount of space and time.

What is Divide and Conquer Algorithm??

The problem at hand is divided into smaller sub-problems, which are then solved separately in the divide and conquer process. We can eventually reach a point where no further division is possible if we continue to divide the subproblems into smaller subproblems.

The smallest possible sub-problems (fractions) are solved at the “atomic” level. The solutions to all sub-problems are then combined to produce the solution to the original problem.

Broadly, we can understand divide-and-conquer approach in a three-step process.

Divide/Break —

This move entails breaking the issue down into smaller sub-parts. Sub-problems should be a subset of the main problem. This move divides the problem in a recursive manner until no further sub-problems can be separated.

Sub-problems become atomic in nature at this stage, but they still represent a portion of the larger question.

Conquer/Solve —

This phase is charged with overcoming a slew of smaller sub-problems. At this stage, problems are usually considered solved on their own.

Merge/Combine —

Until formulating a solution to the original problem, this stage recursively incorporates the smaller sub-problems.

This algorithmic approach is recursive, and the conquer and merge phases are so similar together that they appear to be one.

So, here is a clear demonstration of how this algorithm works

Here, we will sort an array using the divide and conquer approach-

1. So, let the given array be:

2. The collection will be divided into two halves in the next step so that we can quickly find the solution. This is a recursive approach for splitting the problem until there are no more sub-problems that can be divided.

3. So, moving on to the next level, we can recursively divide each subpart into two halves until we get individual components, since dividing this subpart into smaller parts would help us solve the algorithm much better and faster, and this is the divide and conquer algorithm in action.

As a consequence, in any case, we can get the desired output of the problem.

4. Now, We can see in the concluding section above that the subparts have been separated in such a way that we get all of the subparts individually, and therefore the step above is the second part of our method that is being explained here.

Following the completion of the individual parts, we must now combine all of the individual parts in a sorted fashion, resulting in an array that is sorted in a divide and conquer process.

Here is the final sorted array after merging the subparts –

The divide and conquer algorithm is one of the most commonly used methods for solving an unsorted array and completing it in a sorted manner.

The Divide & Conquer strategy is used to create the basic computer algorithms:

1.Maximum and Minimum problem

2.Binary Search

3.Sorting (merge sort, quick sort)

The Hanoi Tower is number four on the list.

The fundamentals of the Divide and Conquer strategy are as follows:

The Divide and Conquer Strategy is based on two principles:

1.Relational Formula
2.Stoppage Condition

Below is a more detailed explanation of these two conditions –

1. Relational Formula:

It’s the formula we come up with as a result of the process. After generating the formula, we employ the D&C method, which involves recursively breaking the problem and solving the broken subproblems.

2. Stopping Condition:

If we use the Divide and Conquer Approach to solve a problem , we need to know how long we can use divide and conquer for.

The situation in which we must interrupt our D&C recursion steps is referred to as the Stopping Condition.

Time Complexity-

The divide and conquer algorithm’s complexity is calculated using the master theorem.

T(n) = aT(n/b) + f(n), where n is the size of the input and an is the number of recursive subproblems.

n/b reflects the size of each subproblem. The scale of all subproblems is considered to be the same.

f(n) = cost of work performed outside of the recursive call, including the cost of splitting the problem and combining the solutions.

Consider the following scenario for determining the time complexity of a recursive issue.

The equation for a merge type is as follows:

T(n) = aT(n/b) + f(n)

= 2T(n/2) + O(n)

In this case,

a = 2 (A problem is divided into two subproblems each time)

n/b = n/2 (each subproblem is half the size of the input)

f(n) is the time it took to break the issue into subproblems and merge them.

O(n log n) = T(n/2) (Please refer to the master theorem to understand this.)

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

≈ O(n log n)

Advantages of Divide and Conquer –

o Divide and Conquer is a technique that has been used to solve some of the world’s most challenging problems, such as the Tower of Hanoi, a mathematical puzzle. It’s difficult to solve complex problems about which you have no clear understanding, but the divide and conquer method has made it easier by splitting the main problem into two halves and then solving them recursively. This algorithm is substantially faster than others.

o Since it solves basic subproblems inside the cache memory rather than accessing the slower main memory, It efficiently utilises cache memory while consuming limited storage space.

o It outperforms its Brute Force counterpart in terms of performance. These algorithms do not need any changes and can be handled by systems that use parallel processing because they avoid parallelism.

Divide and Conquer Applications —

• Binary search
• Merge sort
• Quick sort
• Strassen’s Matrix multiplication
• Karatsuba Algorithm