Merge sort uses divide and conquer algorithm to sort the elements. Since it divides the array equally into two parts recursively, the time complexity in all the cases is O(n * log n). The recursive equation is be T(n) = 2*T(n/2) + n The 2*T(n/2) term appeared because we are dividing the list into two equal part recursively and n is added for merging the list at each step.
Divide and Conquer
Divide and Conquer works by dividing the problem into sub-problems, conquer each sub-problem recursively and combine these solutions.
Dynamic Programming
Dynamic Programming is a technique for solving problems with overlapping subproblems. Each sub-problem is solved only once and the result of each sub-problem is stored in a table ( generally implemented as an array or a hash table) for future references. These sub-solutions may be used to obtain the original solution and the technique of storing the sub-problem solutions is known as memoization.
You may think of DP = recursion + re-use (Ref - http://stackoverflow.com/questions/13538459/difference-between-divide-and-conquer-algo-and-dynamic-programming )
DP = recursion + re-use (Ref -
)
when computation is cheaper than re-computation ?
64.3k questions
77.9k answers
244k comments
80.0k users