On Jun 28, 3:27 pm, UMESH KUMAR <kumar.umesh...@gmail.com> wrote: > 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
Yes. But there is a trivial modification to Quicksort that keeps the stack size from growing beyond O(log n) worst case. Just check the two halves of the partition. Recur first to handle the shortest one. The second recursive call (for the longer half of the partition) is now a tail call that can be converted to a loop. The loop requires no extra stack space. A good compiler optimizer will convert the tail call for you. Otherwise you'll need to code it yourself. Look up "tail recursion elimination." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
