Divide And Conquer Algorithm Vs Dynamic Programming

What is an Algorithm??

abhishek pratapa
5 min readMar 24, 2021

Algorithms are essentially a set of instructions that must be followed in order to accomplish a task or solve a problem. Algorithms are present in all of our activities.

Algorithms provide computers with a step-by-step guide to completing tasks. They are made up of a lengthy list of instructions that explain how to accomplish a particular mission.

How do computer algorithms works??

Input and output are how computer algorithms operate. They take the information as input and add each step of the algorithm to it to produce an output.

A search engine, for example, is an algorithm that accepts a search query as input and searches its database for objects that match the terms in the query. The results are then output.

Algorithms can be conveniently visualised as flowcharts. The data generates a series of steps and questions that must be addressed in a specific order. The created result is the output when each portion of the flowchart is completed.

Divide and Conquer Algorithm:

Both merge sort and quicksort use the same recursive algorithmic paradigm. Divide-and-conquer splits a problem into subproblems that are identical to the original problem, solves the subproblems recursively, and then combines the subproblem solutions to solve the original problem. Since divide-and-conquer recursively solves subproblems, each subproblem must be smaller than the original problem, and subproblems must have a base case. A divide-and-conquer algorithm can be broken down into three parts:

1. Divide/Break:

Breaking the problem down into smaller sub-problems is the next step. Sub-problems should be a subset of the main problem. This move divides the problem in a recursive manner until no further sub-problems can be separated. Sub-problems become atomic in nature at this stage, but they still reflect a portion of the larger problem.

2. Conquer/Solve:

This step receives a lot of smaller sub-problems to be solved. Generally, at this level, the problems are considered ‘solved’ on their own.

3. Merge/Combine:

As the smaller sub-problems are solved, this stage combines them in a recursive manner until the original problem is solved. This algorithmic approach is recursive, and the conquer and merge phases are so similar together that they appear to be one.

Examples:

The following computer algorithms are based on divide-and-conquer programming approach −

  • Merge Sort
  • Quick Sort
  • Binary Search
  • Strassen’s Matrix Multiplication
  • Closest pair

Time Complexity:

The divide and conquer algorithm’s complexity is calculated using the master theorem.

T(n) = aT(n/b) + f(n), where n is the size of the input and an is the number of recursive subproblems.

n/b reflects the size of each subproblem. The scale of all subproblems is considered to be the same.

f(n) = cost of work performed outside of the recursive call, including the cost of splitting the problem and combining the solutions.

Consider the following scenario for determining the time complexity of a recursive issue.

The equation for a merge type is as follows:

T(n) = aT(n/b) + f(n)= 2T(n/2) + O(n)

In this case,

a = 2 (A problem is divided into two subproblems each time)

n/b = n/2 (each subproblem is half the size of the input)

f(n) is the time it took to break the issue into subproblems and merge them.

O(n log n) = T(n/2) (Please refer to the master theorem to understand this.)

Now, T(n) = 2T(n log n) + O(n)

≈ O(n log n)

Dynamic Programming:

Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into smaller subproblems and taking advantage of the fact that the best solution to the overall problem is decided by the best solution to its subproblems.

Let’s take the example of the Fibonacci numbers. As we all know, Fibonacci numbers are a series of numbers in which each number is the sum of the two preceding numbers. The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, and 8, and they continue on from there.

If we are asked to calculate the nth Fibonacci number, we can do that with the following equation,

Fib(n) = Fib(n-1) + Fib(n-2), for n > 1

As we can clearly see here, to solve the overall problem (i.e. Fib(n)), we broke it down into two smaller subproblems (which are Fib(n-1) and Fib(n-2)). So, we can use Dynamic Programming to solve this problem.

There are two ways of solving a problem with Dynamic Programming:

Ø Memoization: We strive to solve the larger problem by recursively solving smaller sub-problems in memoization. We cache the product of any sub-problem we solve so that we don’t have to solve it again if it’s called several times. We may easily return the saved result instead. Memoization is a method of storing the outcomes of previously solved subproblems.

Ø Tabulation: Tabulation, on the other hand, prevents recursion and is the polar opposite of the top-down method. In this method, we solve the problem by first resolving all of the sub-problems. This is usually accomplished by populating an n-dimensional table. The solution to the top/original problem is then computed based on the table’s results. Tabulation is the polar opposite of Memoization, in which we solve the problem and keep track of previously solved sub-problems. To put it another way, we do memoization in the sense that we solve the most difficult problem first.

Dynamic programming doesn’t have a time complexity, because it is not a specific algorithm.

It’s a general approach to constructing algorithms to solve problems that have certain properties.

Divide and Conquer (D & C) vs Dynamic Programming (DP)

Both paradigms (D & C and DP) separate and solve subproblems within the given problem. How do you pick one for a particular problem? When the same subproblems are not tested repeatedly, Divide and Conquer can be used. Otherwise, you can use Dynamic Programming or Memoization. For example, Binary Search is a Divide and Conquer algorithm, we never evaluate the same subproblems again. On the other hand, for calculating the nth Fibonacci number, Dynamic Programming should be preferred.

Thanks for reading and I hope you enjoyed it!!

--

--

No responses yet