This algorithm has three steps:<\/span><\/p>\n 1. Divide<\/strong>: divide the larger problem into multiple subproblems.<\/span><\/p>\n 2. Conquer<\/strong>: recursively solve every subproblem individually.<\/span><\/p>\n 3. Combine<\/strong>: combine all the solutions of all the subproblems to get the solution to the whole problem.<\/span><\/p>\n The divide and conquer strategy of designing algorithms has two fundamentals :<\/span><\/p>\n 1. Relational formula<\/b><\/p>\n It is the formula generated from a given technique. After generating the formula, we apply the divide and conquer strategy to break the problem into many subproblems and solve them individually.<\/span><\/p>\n 2. Stopping condition<\/b><\/p>\n When you divide the problem by divide and conquer strategy, you need to understand for how long you have to keep dividing. You have to put a stopping condition to stop your recursion steps.<\/span><\/p>\n Recurrence relation for divide and conquer is given by:<\/span><\/p>\n T(n) = aT(n\/b) + f(n), where a > 1 and b > 1<\/span><\/p>\n We solve the above recurrence relation using the Mas<\/span>ter Method. <\/span>It is a direct way of getting a solution to recurrence relations for divide and conquer algorithms. There are three cases:<\/span><\/p>\n Let a recurrence relation be\u00a0 :\u00a0<\/span><\/p>\n T(n) = 2T(n\/2) + cn. Here a=2,b=2,k=1.<\/span><\/p>\n Log<\/span>b<\/span><\/sub>a = log<\/span>2<\/span><\/sub>2 =1 = k.<\/span><\/p>\n Complexity :\u00a0 \u0398(nlog2(n))<\/span><\/p>\n For example:<\/span><\/p>\n For merge sort:<\/b> recurrence relation : T(n) = 2T(n\/2) + \u0398(n). Here, c=1 and log<\/span>b<\/span><\/sub>a=1.\u00a0 The complexity of merge sort come out to be \u0398(n log n).<\/span><\/p>\n 1. Divide and conquer successfully solved one of the biggest problems of the mathematical puzzle world,\u00a0 the tower of Hanoi. <\/span><\/p>\n You might have a very basic idea of how the problem is going to be solved but dividing the problem makes it easy since the problem and resources are divided.<\/span><\/p>\n 2. Is very much faster than other algorithms.<\/span><\/p>\n 3. The divide and conquer algorithm works on parallelism. Parallel processing in operating systems handles them very efficiently.<\/span><\/p>\n 4. The divide and conquer strategy used cache memory without occupying much main memory. Executing problem in cache memory which is faster than main memory.<\/span><\/p>\n 5. Brute force technique and divide and conquer techniques are similar but divide and conquer is more proficient<\/span><\/p>\n 1. Most of the divide and conquer design uses the concept of recursion therefore it requires high memory management.<\/span><\/p>\n 2. Memory overuse is possible by an explicit stack.<\/span><\/p>\n 3. It may crash the system if recursion is not performed properly.<\/span><\/p>\n Both divide and conquer and dynamic programming divides the given problem into subproblems and solves those problems. Dynamic programming is used where the same problem is required to be solved again and again, whereas divide and conquer is used where the same problem is not required to be calculated again.<\/p>\n For example, in the merge sort algorithm, we don’t need to calculate the same subproblem again, but while calculating the Fibonacci series we need to calculate the sum of the past two numbers again and again to get the next number. So we use dynamic programming in this case.<\/p>\n Let us see an example for better understanding.<\/p>\n Arrange the letter of the word \u201cDATAFLAIR\u201d alphabetically using the merge sort technique.<\/p>\n![\"Divide](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Divide-and-conquer-normal-images01.jpg\")
<\/a><\/p>\nFundamentals of divide and conquer algorithm<\/h3>\n
\n
Divide and conquer recurrence relations<\/h3>\n
\n
Advantages of Divide and Conquer Algorithm<\/h3>\n
Disadvantages of Divide and Conquer Algorithm<\/h3>\n
Divide and conquer algorithm vs dynamic programming<\/h3>\n