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
- How Divide and Conquer Algorithms Work?
- Applications of Divide and Conquer Algorithm
- Example of Divide and Conquer Algorithm
- Advantages of Divide and Conquer Algorithm
- Disadvantages of Divide and Conquer Algorithm
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.
- Assume the given array is:
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 Criteria, GATE 2024, GATE Admit Card, GATE Application Form, GATE Syllabus, GATE Cutoff, GATE Previous Year Question Paper, and more.
