Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests - Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests -

Divide and Conquer Algorithm

In computer science, divide and conquer is one of the most popular algorithms. This algorithm splits down a problem into two or more sub-part until they become uncomplicated to solve the problem directly.

Table of Contents

More about Divide and Conquer Algorithm

A divide-and-conquer is a technique of estimating a large problem by:

  • Splitting the problem into sub-parts
  • Resolving the related problems
  • Mixing them together will produce the final output

How Divide and Conquer Algorithms Work?

Here are the steps involved:

  • Divide: In this step, we will break the problem into sub-parts by utilising recursion.
  • Conquer: We will solve the smaller sub-parts recursively. If the subproblem is small, then we can solve it instantly.
  • Combine: Merge the solutions of the sub-parts of the problems to solve the actual problem.

Applications of Divide and Conquer Algorithm

The applications of the Divide and Conquer algorithm are as follows:

  • Binary Search
  • Merge Sort
  • Quick Sort
  • Strassen’s Matrix Multiplication
  • Karatsuba Algorithm
  • Strassen’s Algorithm
  • Cooley-Tukey Fast Fourier Transform (FFT) Algorithm
  • Karatsuba Algorithm for Fast Multiplication

Example of Divide and Conquer Algorithm

Here, we will sort an array using the divide and conquer approach, i.e. merge sort.

  1. Assume the given array is:

Divide and Conquer Algorithm 1

2. Break the array into two segments.

Recursively split each subpart again into two parts until you have separate elements.

3. Merge the individual parts in an ordered manner. Here, the steps to conquer and merge go hand in hand.

Advantages of Divide and Conquer Algorithm

  • It efficiently uses cache memory without occupying much space because it solves simple subproblems within the cache memory instead of accessing the slower main memory.
  • It’s more effective than the Brute Force approach.
  • Due to the fact that these techniques avoid parallelism, it is handled by systems that use parallel processing without requiring any adjustment.

Disadvantages of Divide and Conquer

  • Recursion is incorporated into the majority of its algorithms; hence it requires intensive memory management.
  • The space could be overused by an explicit stack.
  • If the recursion is carried through rigorously beyond the CPU stack, the system can even crash.

Keep learning and stay tuned to BYJU’S to get the latest updates on GATE Exam along with GATE Eligibility CriteriaGATE 2024GATE Admit CardGATE Application FormGATE SyllabusGATE CutoffGATE Previous Year Question Paper, and more.