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
<[email protected]>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 [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.
>
--
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 [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.
