in Interview Questions
677 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 ?
in Interview Questions
677 views

3 Answers

3 votes
3 votes
Best answer

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 comment

when computation is cheaper than re-computation ?

0
0
1 vote
1 vote
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 vote
1 vote
2 answers
1
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true