Space required for MERGE SORT is* O(logn)*
Because the based on Dived And Conquer every level dived size of n/2
So height of the tree is *logn* .And each level take cost O(n)
Recrsn Eqn:
T(n) =O(1) if n=1.
T(n) =2T(n/2) +Cn otherwise
Total cost=O(nlogn)
in which cost of merge procedure =O(n)
and cost of Merge Sort=O(logn)
//*********************************************************************
But in Quick Sort O(n) in Worst case
Because This cost depends on Partition so in Worst case
Partition Devid in (n-1) 0
1 ,2,3,46,79,7,5,4,44
n=9;
Partition :-
1 ) 8 0
2) 7 0
3) 6 0 and so on
Recu EQ:-
T(n) = T(n-1) + T(0) +O(1)
so total cost =O(n^2)
So we can say number of call from the Quick Sort to the Partition is N
So,We can say in cost of Quick sort=O(n).
UMESH KUMAR
PERSUING MCA FROM
D.U
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
