In order to find the median of an unsorted you can do it in O(n) time complexity.You can do it as J.Guo said,but you need from the quicksort the select subroutine.Try googling some keywords: select,quicksort,median-select,k-th element. Tarjan,etc proved that median can be done in O(n)(also i believe that it may be in place procedure) I don't know but according to the recurrence relation that you gave ,the algoritihm divide the problem into 3 of n/2 size.Why you have this?
Do you try something like that: Assumed an array a1,a2,.....a(n/2)........a(n) and partition in 1)a(1).....a(n/2) 2)a(n/2+1)....a(n) 3) a((n/2+1)/2)....a(9n/2+n)/2)(which is from the median of 1) until median of 2) Why you are doing this?Explain your intuition for the recurrence relation(because of your constraint for a È(í^ln3)? --~--~---------~--~----~------------~-------~--~----~ 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-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
