Divide And Conquer : Here to Rescue

Pratham Gupta | E19CSE034 | Bennett University

This topic is related to a strategy for solving a problem. If a problem P of some size is given and let us take the size as N. This size is the input for the problem. And if we say that this problem is large for the application of the strategy then we can say that it can be divided into subproblems (P1, P2, P3, …., Pk). Now these subproblem can be solved to obtain the solutions (S1, S2, S3, …., Sk). All these are individually solved. Now once we have all these solutions then combine these solutions to get the solution for main problem.

Generalised snapshot of how this strategy works.

The three main steps in the Divide and Conquer paradigm are:

• Divide : involves breaking the main problem into tinier, non-overlapping sub-problems.
• Conquer : involves solving the sub-problems in recursive manner.
• Combine : involves merging the solutions of those sub-problems to solve the main problem.

If in case a subproblem is also large to solve then in that case also we will use divide and conquer technique. Break it into sub-sub problems and find the sub-sub solutions for the same.

Now one important thing about divide and conquer is whatever the problem is sub problems will be same as that problem. For e.g. If a problem is to sort the sub problems should also be sort. It cannot be converted into some other problem. So, this is how it is recursive in nature.

When we have broken the problem into sub problems then we should have some methods to combine their solutions to get a main solution. If we are unable to combine, then we cannot adopt this strategy.

General Algorithm for divide and conquer strategy:

The following algorithms are based on Divide-And-Conquer approach which justifies implications :

• Quick Sort
• Merge Sort
• Strassen’s Matrix Multiplication
• Binary Search
• Closest Pair of Points

Quick Sort, Merge Sort and Binary Search are the most famous Divide and Conquer algorithms.

To have the in-depth insight of how this strategy works, let us have the look on one simple algoritm of Binary Search :-

Binary search is one of thedivide and conquer algorithm to help with the mentioned problem. This search algorithm recursively divides the array into sub-arrays that may contain the search element. It discards the sub-array by the fact that items are sorted sequentially. It proceeds dividing the sub-arrays until it finds the search element or it comes down the array to a single element. The time complexity of mentioned Binary Search is O(log N), where N is the number of elements in an array depicting the source.

If the search element is present at the centre of the array, it’s considered to be the best case since the element is found instantly. Hence the best case complexity is O(1).

To know more about the same we will now look at the worst timecomplexity of Binary Search :

• N = 16 (no. of elements in the sorted array)

Image Credits: Hacker Noon

• The centre element is made pivot

• As the array is sorted, and 13 is less than the pivot element, the other half of the array is removed.

• Then the same process is repeated of dividing the arrays into sub arrays.

• The array was summoned 4 times to reach the desired element in an array. Therefore,

• Therefore, for N elements:

• Multiplying both left and right sides by (2^k)

• Solution :-

We have got the O(log n) time complexity !

How it came into the Picture ? (History)

It originated from the Latin Phrase “ divide et impera ”.

Many rulers have adopted this strategy in their reign.

Let’s have a look at Pros of Divide And Conquer Strategy :

• Solves complex and difficult problems with less time complexity than the brute-force counterpart algorithm.
• As the sub-problems are independent, they can be solved in parallel manner easily.
• It suits best for multiprocessing systems.
• Efficient usage of Memory Caches.

It is associated with Cons too when it comes into picture :

• Recursion into smaller bits may or eventually lead to large recursive stacks.
• Involves recursion which takes more space thus making Space complexity larger.

How Dynamic Programming is different from Divide And Conquer ?

• Dynamic Programming is Non-Recursive in nature but its opposite in the case of Divide And Conquer.
• Dynamic Programming follows Bottom-Up Approach but its vice versa in the case of Divide And Conquer Method.
• In Dynamic Programming, the subproblems are interdependent on each other but in the case of DAC, subproblems are independent of each other but follows the properties of main problem.
• In Dynamic Programming, subproblems are solved only one and then stored in the table.
• Dynamic programming is muchmore efficient than Divide and Conquer Method.
• Used by Matrix Chain Multiplication, Optimal Binary Search Tree.

# REAL WORLD IMPLICATIONS :

A divide and conquer marketing strategy revolves around recognising your customers through targeting, segmentation and positioning.

Segmentation Strategy

Segmentation includes dividing the market down into bits based on a number of factors, including:

• Geography
• Demographics
• Behavioral qualities
• Socio-economics

Dividing customers into tinier groups help businesses and companies determine where they should focus their marketing efforts. Like the divide and conquer algorithm, divided groups should not overlap with each other.

Positioning Strategy

With the positioning strategy, team break their product down to show how it’s different, unique and provide more value to a target group in comparison to the competitor’s product.

Targeting Strategy

Marketing Team can also apply this to target specific customers, melting larger groups down into target groups that match a product or service. Within each specific target group, we can find further divisible subgroups that thins the crowd down even further.

How Can Divide and Conquer Increase Sales?

A divide and conquer strategy can be much more useful and effective. Considering Marketing team, team can use divide and conquer strategy to focus on a specific target audience. This strategy helps us to adjust our pitch to match our target audience, resulting in more sales.

Instead of calling every name on a list, finding a particular segment of the population that may be most interested in the product we are selling can be much more effective. We can base our customers on location, industry, age, or other factors.

How We Can Use Divide and Conquer Strategy in Our Everyday Life ?

Using divide and conquer strategy in life can help us in different ways. Here’s how a Divide and Conquer strategy helps us in various aspects :

• Solve Problems
• Improve Efficiency
• Boost Productivity

THANKS FOR VISITING THE BLOG ❤ 🙏🏻