Year End Sale: Get Upto 40% OFF on Live Training! Offer Ending in
D
H
M
S
Get Now
Divide and Conquer Algorithm in Data Structures - Its Working, Advantages & Disadvantages

Divide and Conquer Algorithm in Data Structures - Its Working, Advantages & Disadvantages

06 Jun 2024
Intermediate
10.5K Views
8 min read
Learn with an interactive course and practical hands-on labs

Free Data Structures & Algorithms Foundation Course

Divide and Conquer Algorithm: An Overview

Divide and Conquer Algorithm is a problem-solving method in Data Structures working on recursion principle. We had seen this in brief in the Data Structures and Algorithms tutorial. In this DSA tutorial, we will discuss the Divide and Conquer Algorithm with its working, implementation, etc. To further enhance your understanding and application of Divide and Conquer, consider enrolling in the best Data Structures and Algorithms Course, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is Divide and Conquer Algorithm in Data Structures?

According to the name, the divide and Conquer Algorithm involves breaking down a complex task into smaller, more manageable sub-problems, solving them independently, and then merging the results to obtain the final solution. In this, we keep dividing the given problem into smaller problems to the point that these smaller sub-problems can no longer be further divided.

Working of Divide and Conquer Algorithm

The following three steps are involved in the working of Divide and Conquer Algorithm:

  1. Divide: Divide the given problem into sub-problems until none of the sub-problems are further divisible using recursion.
  2. Conquer: Solve the smaller sub-problems recursively. If the subproblem is small enough, then solve it directly.
  3. Combine: Recursively combine the individual solutions of the sub-problems obtained from the previous stage of the algorithm that are part of the recursive process to solve the actual problem.

Working of Divide and Conquer Algorithm

One can observe that recursion is at the core of the divide-and-conquer algorithms. Whether it is breaking down the original problem into sub-problems or merging the individual solutions into the final solutions, both tasks are done recursively. Thus, to establish a strong understanding of the divide and conquer approach, a good understanding of recursion is mandatory.

Learn more:

Example of Divide and Conquer Algorithm

Here, we will sort an array using the divide and conquer approach (ie. merge sort).

  1. Let the given array be

    Array for merge sort

  2. Divide the array into two halves.

    Divide the array into two halves for merge sort

    Again, divide each subpart recursively into two halves until you get individual elements.

    Divide array into smaller sunparts

  3. Now, combine the individual elements in a sorted manner. Here, conquer and combine steps go side by side.

    Combine the subparts in merge sort

Read More - Data Structure Interview Questions for Freshers

Time Complexity of Divide and Conquer Algorithm

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

T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed to have the same size.
f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions   

Divide and Conquer vs the Dynamic Programming Approach

Both the divide and conquer and the dynamic programming algorithms share a common characteristic: the initial problem is divided into smaller sub-problems, and then the final solution is generated in a bottom-up approach where the resultant outputs of the subproblems are combined into the final solution.

The difference lies in how the sub-problems are solved and merged into the final solution.

  1. The divide and conquer approach divides a problem into smaller subproblems; these subproblems are further solved recursively. The result of each subproblem is not stored for future reference, whereas, in a dynamic approach, the result of each subproblem is stored for future reference.
  2. Use the divide and conquer approach when the same subproblem is not solved multiple times. Use the dynamic approach when the result of a subproblem is to be used multiple times in the future.

Let's take an example to find the Fibonacci series.

Divide and Conquer Approach

fib(n)
    If n < 2, return 1
    Else , return f(n - 1) + f(n -2)  

Dynamic Approach

mem = []
fib(n)
    If n in mem: return mem[n] 
    else,     
        If n < 2, f = 1
        else , f = f(n - 1) + f(n -2)
        mem[n] = f
        return f

Here, we are storing the result of each sub-problem in the memory array, mem. These stored solutions can then be referenced and reused in the future as we are further solving the problem.

Advantages of Divide and Conquer Algorithms

  1. Efficiency: Divide and Conquer algorithms often provide efficient solutions to problems. By breaking down a problem into smaller parts, the algorithm can reduce the overall time complexity of the solution.
  2. Parallelization: They are used in multi-processor machines having shared-memory systems where the communication of data between processors does not need to be planned because distinct sub-problems can be executed on different processors.
  3. Modularity: The algorithm promotes modularity by dividing a complex problem into manageable subproblems. Each subproblem can be solved separately and then combined with other subproblem solutions to obtain the final result.
  4. Algorithmic reusability: The Divide and Conquer approach is often based on recurring patterns. Once a general divide-and-conquer algorithm is designed, it can be applied to problems with similar characteristics.
  5. Solving large instances: Divide and Conquer algorithms are particularly useful when dealing with large problem instances. By dividing the problem into smaller subproblems, the algorithm can handle larger inputs more efficiently.
  6. Optimality: In many cases, these algorithms produce optimal solutions. By solving subproblems optimally and combining the results correctly, the algorithm can guarantee an optimal solution for the overall problem.

Disadvantages of Divide and Conquer Algorithm

  • Extra Memory Usage: In some cases, the divide and conquer approach requires additional memory to store intermediate results during the recursive process. This can be a disadvantage, especially when dealing with large input sizes or limited memory resources.
  • Difficulty Handling Some Problems: Not all problems can be easily solved using the divide and conquer paradigm. Some problems may not have a natural division, or the division process may introduce additional complexities that make the algorithm less efficient or harder to implement correctly.
  • Suboptimal Solutions: The divide and conquer strategy sometimes guarantees the most optimal solution. Although it often leads to efficient solutions, there are cases where alternative algorithms can outperform divide-and-conquer approaches in terms of time or space complexity.
  • Not Always Stable: Divide and conquer algorithms may not preserve the order of elements in the input.
  • Potential for Overlapping Subproblems: Some divide-and-conquer algorithms may encounter overlapping subproblems, meaning that the same subproblem is solved multiple times. Without proper techniques to handle overlapping subproblems, the algorithm can become inefficient due to redundant computations
Summary

Hence, Divide and Conquer algorithm is a powerful tool for solving complex problems with ease. It reduces the complexity of its operations into a series of smaller problems that can be more easily solved, allowing for faster problem-solving processes. This has seen it being used extensively in computer science, mathematics, engineering, cryptography, and many other fields. To test your knowledge of the Divide and Conquer algorithm, enroll in our Dsa Training.

FAQs

In the dynamic approach, the result of each subproblem is stored for future reference whereas it's not so in Divide and Conquer.

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

Divide-and-Conquer algorithms may not preserve the order of elements in the input.
Share Article
About Author
Amit Kumar Ghosh (SDE and Mentor at Scholarhat)

As a software developer with a wealth of experience, he brings a unique combination of technical acumen and a passion for mentorship to my role. With 6 years of experience, he has honed the skills in C/C++, Java, Python, SQL, C#, JavaScript, React, Java Spring etc. and has a proven track record of delivering high-quality, scalable software solutions and core Computer fundamental knowledge DSA, OOPs, CN, OS etc.

As a teacher, his approach revolves around interactive techniques, prioritizing hands-on learning and real-world projects. He explains concepts clearly, offer practical examples, and encourage questions to foster a supportive environment.
Accept cookies & close this