2 votes 2 votes #IISc2012Research 1>Recurrence relation and worst case time complexity of Merge sort 2> Difference between D&C and Dynamic Programming ? Rajesh Pradhan asked Feb 23, 2016 Rajesh Pradhan 734 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes 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 ) monanshi answered Feb 26, 2016 • selected Jul 12, 2017 by monanshi monanshi comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes 1.worst case complexity of merge sort is O(nlogn) and recurrence is t(n)=2t(n/2)+n.................. 2. its better to refer cormen .........divide and con.. in this approach we divide the prblm into subprblem and combine the results of subprblm so that it give solution to problem...... but in dynamic programming we save the smaller result in table and refer to that table when computation is cheaper than re-computation....... khamer answered Feb 23, 2016 khamer comment Share Follow See 1 comment See all 1 1 comment reply Himanshu1 commented Feb 25, 2016 reply Follow Share when computation is cheaper than re-computation ? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes in DIVIDE AND CONQUER the sub problems are indepent of each other.e.g. binary search,merge sort,etc. wherease in dynamic the is sub-optimal structure and these sub problems are dependent on each other.cormen is the best book for this. viv696 answered Feb 24, 2016 viv696 comment Share Follow See all 0 reply Please log in or register to add a comment.