A WHOLE NEW WORLD OF DIVIDE AND CONQUER…

Explanation of Algorithm

WORKING…

The following 3 steps shows the way in which Divide and Conquer Algorithm works :-

  1. DIVIDE- A problem should be broken down into smaller problems.
  2. CONQUER- Understand and solving the sub problems separately.
  3. COMBINE- Then combine them and get the output.
Example showing sorting an array using Divide and Conquer.

ADVANTAGES…

  1. MAKING PROBLEMS EASIER:- Divide and conquer is a powerful way to solve complex psychological problems: all you need is a way to break the problem into smaller problems, solve smaller cases, and then combine small problems to solve real problems
  2. EFFICIENCY OF ALGORITHMS:- The strategy of divide and conquer is often used to acquire effective skills. It has been used in Karatsuba’s rapid replication process, quick sort and merge sort algorithms, Strassen matrix multiplication algorithm, and Fourier variable, among other things.
  3. PARALLELISM:- Divide and Conquer algorithms are well suited to most processor machines, especially shared memory systems, where data communication between processors does not need to be pre-programmed because minor problems below can be solved on different processors.
  4. MEMORY MANAGEMENT:- This algorithm uses memory caches in an efficient manner.
  5. ROUNDOFF CONTROL:- This algorithm can produce more accurate results than the same recurring method in multiplication by rounded numbers, such as floating point numbers.

TIME COMPLEXITY…

The complexity of the time algorithm means the time it takes for the system to start from start to finish. Capital ‘O’ notation is widely used to express the time complexity of algorithms. The number of basic tasks performed by the algorithm is widely used to estimate the complexity of time, assuming that each basic task takes a set amount of time to complete. In the case of Divide and Conquer, Master’s theorem is used to calculate the time complexity.

Master’s Theorem

IMPLEMENTATION ISSUES…

  1. RECURSION:- Recursive functions are used to implement divide and conquer algorithm. In that case, the procedure call stack automatically stores the partial sub-problems that correspond to the one currently being solved. A recursive function is one that calls itself within the function.
  2. EXPLICIT STACK:- Non-recursive programs that store partial sub-problems in an explicit data structure, such as a stack, queue, or priority queue, may also be used to implement divide-and-conquer algorithms. This method provides more flexibility in selecting the underlying problem to be solved, which is required for other applications.
  3. STACK SIZE:- When using recursive Divide & Conquer algorithms, make sure there is enough memory allocated to the return stack; otherwise, processing may fail due to stack overflow.
  4. CHOOSING THE BASE CASES:- In any recursive algorithm, the option of the base cases, or tiny subproblems that are solved directly to end the recursion, has a lot of latitude.
  5. REPEATED SUBPROBLEMS:- Branch recurrence can end up examining the same problem over and over again in other problems. It would be good to find and keep solutions to these conflicting problems in such cases.

DIVIDE AND CONQUER VS DYNAMIC APPROACH…

The process of dividing and conquering divides the problem into smaller, more complex problems. The outcome of each problem is not stored for future reference, while the results of each problem are stored for future use in a more efficient way. If the same small problem can be solved several times, use a strategy to divide and conquer. If the result of the problem below is not used several times in the future, use dynamic approach.

Divide and Conquer Approach
Dynamic Approach (result of each problem is saved in ‘mem’)

WHEN SHOULD YOU USE DIVIDE AND CONQUER…

It will be useful if we have a problem similar to the well-known divide and conquer algorithm (such as merge sort).Most of the time, we will build algorithms that are very close to compiling the form. We will be able to use divide and conquer if we have an algorithm that takes a list and does something with each item in the list. If we have a sluggish algorithm and want to expand it, one of our first decisions is to divide and conquer. If we have a frustrated algorithm and want to boost it, one of our first decisions would be to use divide and conquer.

TO CUT A LONG STORY SHORT…

Once you have identified that this is the problem where you can use divide and conquer, then it becomes an easy job. The real work is performed in three stages: partitioning problems into subproblems, solving subproblems outright at the very end of the recursion, and gluing together partial answers. The algorithm’s central recursive structure binds them all together and coordinates them and thus speeds up the algorithm. Now that you know all this, you won’t have any problem in solving problems related to divide and conquer algorithm.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store