Another question reg. quicksort. If we always find the median in o(n) and use it as the pivot ,will the quicksort by o(nlogn) ( i mean worst case also o(nlogn) )?
Since partition is anyway o(n) , im making it o(n) + o(n){for finding median}. On Wed, Jul 6, 2011 at 2:50 AM, Ritesh Srivastava <riteshkumar...@gmail.com>wrote: > It will be O (n*log(n)). > Recurrence relation will be > > T(n) = T(n/4) + T(3n/4) + O(n) > > Lets just say > > n=4^p > so p=log n in base 4 > so this will be the number of steps the array will be divided to get > trivial constant size array. > at every step , processing done will be O(n) because > > n -- > for first step > (n/4) +(3n/4) --> for second step == n/4 for the first partition and 3n/4 > for the second partition obtained in the first step > ( n/4 * 1/4 + n/4 * 3/4) + ( 3n/4*1/4 + 3n/4*3/4) -->third step > ... > ... > so on > for logn steps. > Hence O(n *logn ) Omitting constant factor of base 4. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/THiTmtrNhogJ. > > To post to this group, send email to algogeeks@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. > -- regards, chinna. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.