Otherwise, if x is less than the middle element, then the algorithm recurs to the left side of the middle element, else it recurs to the right side of the middle element. If the values match, return the index of middle. In each step, the algorithm compares the input element (x) with the value of the middle element in array. Linear Search has time complexity O(n), whereas Binary Search (an application Of Divide And Conquer) reduces time complexity to O(log(n)).įollowing are some standard algorithms that are of the Divide and Conquer algorithms variety.īinary Search is a searching algorithm. This method usually allows us to reduce the time complexity by a large extent.įor example, Bubble Sort uses a complexity of O(n^2), whereas quicksort (an application Of Divide And Conquer) reduces the time complexity to O(nlog(n)). This algorithmic approach works recursively and conquer & merge steps works so close that they appear as one.

When the smaller sub-problems are solved, this stage recursively combines them until they formulate a solution of the original problem. Combine: Appropriately combine the answers.Generally, at this level, the problems are considered 'solved' on their own. This step receives a lot of smaller sub-problems to be solved. Conquer: Recursively solve these sub-problems.At this stage, sub-problems become atomic in nature but still represent some part of the actual problem. This step generally takes a recursive approach to divide the problem until no sub-problem is further divisible. Sub-problems should represent a part of the original problem. This step involves breaking the problem into smaller sub-problems. Divide: Break the given problem into subproblems of same type.A typical Divide and Conquer algorithm solves a problem using the following three steps. What are Divide and Conquer Algorithms? (And no, it's not 'Divide and Concur')ĭivide and Conquer is an algorithmic paradigm (sometimes mistakenly called 'Divide and Concur' - a funny and apt name), similar to Greedy and Dynamic Programming.

Split and conquer