683 views
2 votes
2 votes
#IISc2012Research 1>Recurrence relation and worst case time complexity of Merge sort 2> Difference between D&C and Dynamic Programming ?

3 Answers

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 )
 

selected by
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.......
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.

Related questions

1 votes
1 votes
2 answers
1
Rajesh Pradhan asked Feb 23, 2016
330 views
#IISc2012Research Rank of a matrix, a (i,j)=0,if i+j odd, else 1
0 votes
0 votes
0 answers
2
sonucse12345 asked May 29, 2023
94 views
please anyone share iit patna self sponsored interview experience for artificial intelligence mtech 2022 ?
1 votes
1 votes
0 answers
3
Vivekk asked Feb 14, 2019
494 views
Hi, I am getting a score around 600 as per GO.I have done my BTech in Electrical Engineering in 2018 and have a CGPA of 8.02.What are the possible options in IITs for Res...