Open In App

Introduction to Divide and Conquer Algorithm – Data Structure and Algorithm Tutorials

Last Updated : 01 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Divide and Conquer Algorithm is a problem-solving technique used to solve problems by dividing the main problem into subproblems, solving them individually and then merging them to find solution to the original problem. In this article, we are going to discuss how Divide and Conquer Algorithm is helpful and how we can use it to solve problems.

Introduction-to-Divide-and-Conquer-Algorithm-(1)

Divide and Conquer Algorithm Definition:

Divide and Conquer Algorithm involves breaking a larger problem into smaller subproblems, solving them independently, and then combining their solutions to solve the original problem. The basic idea is to recursively divide the problem into smaller subproblems until they become simple enough to be solved directly. Once the solutions to the subproblems are obtained, they are then combined to produce the overall solution.

Working of Divide and Conquer Algorithm:

Divide and Conquer Algorithm can be divided into three steps: Divide, Conquer and Merge .

Working-of-Divide-and-Conquer-Algorithm

1. Divide:

  • Break down the original problem into smaller subproblems.
  • Each subproblem should represent a part of the overall problem.
  • The goal is to divide the problem until no further division is possible.

2. Conquer:

  • Solve each of the smaller subproblems individually.
  • If a subproblem is small enough (often referred to as the “base case”), we solve it directly without further recursion.
  • The goal is to find solutions for these subproblems independently.

3. Merge:

  • Combine the sub-problems to get the final solution of the whole problem.
  • Once the smaller subproblems are solved, we recursively combine their solutions to get the solution of larger problem.
  • The goal is to formulate a solution for the original problem by merging the results from the subproblems.

Characteristics of Divide and Conquer Algorithm:

Divide and Conquer Algorithm involves breaking down a problem into smaller, more manageable parts, solving each part individually, and then combining the solutions to solve the original problem. The characteristics of Divide and Conquer Algorithm are:

  • Dividing the Problem: The first step is to break the problem into smaller, more manageable subproblems. This division can be done recursively until the subproblems become simple enough to solve directly.
  • Independence of Subproblems: Each subproblem should be independent of the others, meaning that solving one subproblem does not depend on the solution of another. This allows for parallel processing or concurrent execution of subproblems, which can lead to efficiency gains.
  • Conquering Each Subproblem: Once divided, the subproblems are solved individually. This may involve applying the same divide and conquer approach recursively until the subproblems become simple enough to solve directly, or it may involve applying a different algorithm or technique.
  • Combining Solutions: After solving the subproblems, their solutions are combined to obtain the solution to the original problem. This combination step should be relatively efficient and straightforward, as the solutions to the subproblems should be designed to fit together seamlessly.

Examples of Divide and Conquer Algorithm:

1. Finding the maximum element in the array:

We can use Divide and Conquer Algorithm to find the maximum element in the array by dividing the array into two equal sized subarrays, finding the maximum of those two individual halves by again dividing them into two smaller halves. This is done till we reach subarrays of size 1. After reaching the elements, we return the maximum element and combine the subarrays by returning the maximum in each subarray.

C++
// function to find the maximum no.
// in a given array.
int findMax(int a[], int lo, int hi)
{
    // If lo becomes greater than hi, then return minimum
    // integer possible
    if (lo > hi)
        return INT_MIN;
    // If the subarray has only one element, return the
    // element
    if (lo == hi)
        return a[lo];
    int mid = (lo + hi) / 2;
    // Get the maximum element from the left half
    int leftMax = findMax(a, lo, mid);
    // Get the maximum element from the right half
    int rightMax = findMax(a, mid + 1, hi);
    // Return the maximum element from the left and right
    // half
    return max(leftMax, rightMax);
}
Java
// Function to find the maximum number
// in a given array.
static int findMax(int[] a, int lo, int hi)
{
    // If lo becomes greater than hi, then return
    // minimum integer possible
    if (lo > hi)
        return Integer.MIN_VALUE;
    // If the subarray has only one element, return the
    // element
    if (lo == hi)
        return a[lo];
    int mid = (lo + hi) / 2;
    // Get the maximum element from the left half
    int leftMax = findMax(a, lo, mid);
    // Get the maximum element from the right half
    int rightMax = findMax(a, mid + 1, hi);
    // Return the maximum element from the left and
    // right half
    return Math.max(leftMax, rightMax);
}
Python3
# Function to find the maximum number
# in a given array.
def find_max(a, lo, hi):
    # If lo becomes greater than hi, then return minimum
    # integer possible
    if lo > hi:
        return float('-inf')
    # If the subarray has only one element, return the
    # element
    if lo == hi:
        return a[lo]
    mid = (lo + hi) // 2
    # Get the maximum element from the left half
    left_max = find_max(a, lo, mid)
    # Get the maximum element from the right half
    right_max = find_max(a, mid + 1, hi)
    # Return the maximum element from the left and right
    # half
    return max(left_max, right_max)
C#
// Function to find the maximum number
// in a given array.
static int FindMax(int[] a, int lo, int hi)
{
    // If lo becomes greater than hi, then return
    // minimum integer possible
    if (lo > hi)
        return int.MinValue;
    // If the subarray has only one element, return the
    // element
    if (lo == hi)
        return a[lo];
    int mid = (lo + hi) / 2;
    // Get the maximum element from the left half
    int leftMax = FindMax(a, lo, mid);
    // Get the maximum element from the right half
    int rightMax = FindMax(a, mid + 1, hi);
    // Return the maximum element from the left and
    // right half
    return Math.Max(leftMax, rightMax);
}
JavaScript
// Function to find the maximum number
// in a given array.
function findMax(a, lo, hi) {
    // If lo becomes greater than hi, then return minimum
    // integer possible
    if (lo > hi)
        return Number.MIN_VALUE;
    // If the subarray has only one element, return the
    // element
    if (lo === hi)
        return a[lo];
    const mid = Math.floor((lo + hi) / 2);
    // Get the maximum element from the left half
    const leftMax = findMax(a, lo, mid);
    // Get the maximum element from the right half
    const rightMax = findMax(a, mid + 1, hi);
    // Return the maximum element from the left and right
    // half
    return Math.max(leftMax, rightMax);
}

2. Finding the minimum element in the array:

Similarly, we can use Divide and Conquer Algorithm to find the minimum element in the array by dividing the array into two equal sized subarrays, finding the minimum of those two individual halves by again dividing them into two smaller halves. This is done till we reach subarrays of size 1. After reaching the elements, we return the minimum element and combine the subarrays by returning the minimum in each subarray.

3. Merge Sort:

We can use Divide and Conquer Algorithm to sort the array in ascending or descending order by dividing the array into smaller subarrays, sorting the smaller subarrays and then merging the sorted arrays to sort the original array.

Complexity Analysis of Divide and Conquer Algorithm:

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

Applications of Divide and Conquer Algorithm:

The following are some standard algorithms that follow Divide and Conquer algorithm:

  • Quicksort is a sorting algorithm that picks a pivot element and rearranges the array elements so that all elements smaller than the picked pivot element move to the left side of the pivot, and all greater elements move to the right side. Finally, the algorithm recursively sorts the subarrays on the left and right of the pivot element.
  • Merge Sort is also a sorting algorithm. The algorithm divides the array into two halves, recursively sorts them, and finally merges the two sorted halves.
  • Closest Pair of Points The problem is to find the closest pair of points in a set of points in the x-y plane. The problem can be solved in O(n^2) time by calculating the distances of every pair of points and comparing the distances to find the minimum. The Divide and Conquer algorithm solves the problem in O(N log N) time.
  • Strassen’s Algorithm is an efficient algorithm to multiply two matrices. A simple method to multiply two matrices needs 3 nested loops and is O(n^3). Strassen’s algorithm multiplies two matrices in O(n^2.8974) time.
  • Cooley–Tukey Fast Fourier Transform (FFT) algorithm is the most common algorithm for FFT. It is a divide and conquer algorithm which works in O(N log N) time.
  • Karatsuba algorithm for fast multiplication does the multiplication of two binary strings in O(n1.59) where n is the length of binary string.

Advantages of Divide and Conquer Algorithm:

  • Solving difficult problems: Divide and conquer technique is a tool for solving difficult problems conceptually. e.g. Tower of Hanoi puzzle. It requires a way of breaking the problem into sub-problems, and solving all of them as an individual cases and then combining sub- problems to the original problem.
  • Algorithm efficiency: The divide-and-conquer algorithm often helps in the discovery of efficient algorithms. It is the key to algorithms like Quick Sort and Merge Sort, and fast Fourier transforms.
  • Parallelism: Normally Divide and Conquer algorithms are used in multi-processor machines having shared-memory systems where the communication of data between processors does not need to be planned in advance, because distinct sub-problems can be executed on different processors.
  • Memory access: These algorithms naturally make an efficient use of memory caches. Since the subproblems are small enough to be solved in cache without using the main memory that is slower one. Any algorithm that uses cache efficiently is called cache oblivious.

Disadvantages of Divide and Conquer Algorithm:

  • Overhead: The process of dividing the problem into subproblems and then combining the solutions can require additional time and resources. This overhead can be significant for problems that are already relatively small or that have a simple solution.
  • Complexity: Dividing a problem into smaller subproblems can increase the complexity of the overall solution. This is particularly true when the subproblems are interdependent and must be solved in a specific order.
  • Difficulty of implementation: Some problems are difficult to divide into smaller subproblems or require a complex algorithm to do so. In these cases, it can be challenging to implement a divide and conquer solution.
  • Memory limitations: When working with large data sets, the memory requirements for storing the intermediate results of the subproblems can become a limiting factor.

Frequently Asked Questions (FAQs) on Divide and Conquer Algorithm:

1. What is the Divide and Conquer algorithm?

Divide and Conquer is a problem-solving technique where a problem is divided into smaller, more manageable subproblems. These subproblems are solved recursively, and then their solutions are combined to solve the original problem.

2. What are the key steps involved in the Divide and Conquer algorithm?

The main steps are:

Divide: Break the problem into smaller subproblems.

Conquer: Solve the subproblems recursively.

Combine: Merge or combine the solutions of the subproblems to obtain the solution to the original problem.

3. What are some examples of problems solved using Divide and Conquer?

Divide and Conquer Algorithm is used in sorting algorithms like Merge Sort and Quick Sort, finding closest pair of points, Strassen’s Algorithm, etc.

4. How does Merge Sort use the Divide and Conquer approach?

Merge Sort divides the array into two halves, recursively sorts each half, and then merges the sorted halves to produce the final sorted array.

5. What is the time complexity of Divide and Conquer algorithms?

The time complexity varies depending on the specific problem and how it’s implemented. Generally, many Divide and Conquer algorithms have a time complexity of O(n log n) or better.

6. Can Divide and Conquer algorithms be parallelized?

Yes, Divide and Conquer algorithms are often naturally parallelizable because independent subproblems can be solved concurrently. This makes them suitable for parallel computing environments.

7. What are some strategies for choosing the base case in Divide and Conquer algorithms?

The base case should be simple enough to solve directly, without further division. It’s often chosen based on the smallest input size where the problem can be solved trivially.

8. Are there any drawbacks or limitations to using Divide and Conquer?

While Divide and Conquer can lead to efficient solutions for many problems, it may not be suitable for all problem types. Overhead from recursion and combining solutions can also be a concern for very large problem sizes.

9. How do you analyze the space complexity of Divide and Conquer algorithms?

Space complexity depends on factors like the recursion depth and auxiliary space required for combining solutions. Analyzing space complexity typically involves considering the space used by each recursive call.

10. What are some common advantages of Divide and Conquer Algorithm?

Divide and Conquer Algorithm has numerous advantages. Some of them include:

  • Solving difficult problems
  • Algorithm efficiency
  • Parallelism
  • Memory access

Divide and Conquer is a popular algorithmic technique in computer science that involves breaking down a problem into smaller sub-problems, solving each sub-problem independently, and then combining the solutions to the sub-problems to solve the original problem. The basic idea behind this technique is to divide a problem into smaller, more manageable sub-problems that can be solved more easily.



Previous Article
Next Article

Similar Reads

Difference between Greedy Algorithm and Divide and Conquer Algorithm
Greedy algorithm and divide and conquer algorithm are two common algorithmic paradigms used to solve problems. The main difference between them lies in their approach to solving problems. Greedy Algorithm:The greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage wit
3 min read
Karatsuba algorithm for fast multiplication using Divide and Conquer algorithm
Given two binary strings that represent value of two integers, find the product of two strings. For example, if the first bit string is "1100" and second bit string is "1010", output should be 120. For simplicity, let the length of two strings be same and be n. A Naive Approach is to follow the process we study in school. One by one take all bits o
15+ min read
Comparison among Greedy, Divide and Conquer and Dynamic Programming algorithm
Greedy algorithm, divide and conquer algorithm, and dynamic programming algorithm are three common algorithmic paradigms used to solve problems. Here's a comparison among these algorithms: Approach:Greedy algorithm: Makes locally optimal choices at each step with the hope of finding a global optimum.Divide and conquer algorithm: Breaks down a probl
4 min read
Search in a Row-wise and Column-wise Sorted 2D Array using Divide and Conquer algorithm
Given an n x n matrix, where every row and column is sorted in increasing order. Given a key, how to decide whether this key is in the matrix. A linear time complexity is discussed in the previous post. This problem can also be a very good example for divide and conquer algorithms. Following is divide and conquer algorithm.1) Find the middle elemen
15+ min read
Closest Pair of Points using Divide and Conquer algorithm
We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for dist
15+ min read
Maximum Subarray Sum using Divide and Conquer algorithm
You are given a one dimensional array that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum. For example, if the given array is {-2, -5, 6, -2, -3, 1, 5, -6}, then the maximum subarray sum is 7 (see highlighted elements). Recommended: Please solve it on “PRACTICE ” first, befo
12 min read
Tiling Problem using Divide and Conquer algorithm
Given a n by n board where n is of form 2k where k >= 1 (Basically n is a power of 2 with minimum value as 2). The board has one missing cell (of size 1 x 1). Fill the board using L shaped tiles. A L shaped tile is a 2 x 2 square with one cell of size 1x1 missing. Figure 1: An example inputThis problem can be solved using Divide and Conquer. Bel
15+ min read
Longest Common Prefix using Divide and Conquer Algorithm
Given a set of strings, find the longest common prefix. Examples: Input : {“geeksforgeeks”, “geeks”, “geek”, “geezer”} Output : "gee" Input : {"apple", "ape", "april"} Output : "ap" We have discussed word by word matching and character by character matching algorithms.In this algorithm, a divide and conquer approach is discussed. We first divide th
7 min read
Convex Hull using Divide and Conquer Algorithm
In computational geometry, a convex hull is the smallest convex polygon that contains a given set of points. It is a fundamental concept with applications in various fields such as computer graphics, robotics, and image processing. Importance of Convex Hull:Convex hulls are important in computational geometry for several reasons: Collision detectio
15 min read
Divide and Conquer Algorithm
Divide and Conquer algorithm is a problem-solving strategy that involves breaking down a complex problem into smaller, more manageable parts, solving each part individually, and then combining the solutions to solve the original problem. It is a widely used algorithmic technique in computer science and mathematics. Example: In the Merge Sort algori
4 min read
three90RightbarBannerImg