Let’s explore divide and Conquer : Data Structures and Algorithms

Divide & Conquer Strategy

The “Divide and Conquer” strategy is widely recognized as a fundamental approach to algorithmic problem-solving by programmers across industries. Its simplicity and practicality make it a popular technique for tackling complex problems. In this article, et’s explore divide and Conquer strategy, exploring its key principles and demonstrating its effectiveness in addressing real-world problems.

    A divide-and-conquer strategy recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

    wikipedia.org

    Understanding the divide-and-conquer strategy

    • In simple terms, the divide-and-conquer method involves breaking down (dividing) the complex problem into simple, solvable sub-problems.
    • These sub-problems will be solved independently. If sub-problems are large enough, then these will be further broken down into sub-problems.
    • The generated sub-problems are usually of the same type as the original problem; hence, recursion is used in the divide-and-conquer strategy.

    Control Abstraction of Divide-and-conquer strategy

    Algorithm DandC(P){
      if( isSmall(P))
        return P;
      else{
        Divide P into no. of instances: P1,P2,P3...,Pk;
        Apply DandC(P1), DandC(P2), DandC(P3),...,DandC(Pk);
        return Combine(DandC(P1), DandC(P2), DandC(P3),...,DandC(Pk));
      }
    }
    Computing time for this can be given by recurrence relation:
    T(n) is the time complexity for the divide-and-conquer problem of size n.
    G(n) is the time required to solve the simplified problem.
    F(n) is the time required to divide and combine the solutions of sub-problems.

    Applications of Divide-and-Conquer Strategy

    Let’s explore divide and Conquer !

    Share this article
    Shareable URL
    Comments 1
    Leave a Reply

    Your email address will not be published. Required fields are marked *

    Read next
    Subscribe to our newsletter