Hi, Im a bit confused as how DAndC happens in O(n) time. Doesn't it take O(nlogn) time by the way the algo has been described above? we have to divide the array every time and again work on both the sub arrays. Can you kindly explain how does this take O(n) time?
2008/4/22 Pramod Negi <[EMAIL PROTECTED]>: > make a partition about media as a pivot element > > > On 4/22/08, Varun S V <[EMAIL PROTECTED]> wrote: > > > > Hi Dave, > > > > Can you kindly eloborate your algorithm? > > How can we modify a single array in O(n) time, such that the median > > comes to become the n/2th element and smaller elements comes to the left > > side and larger elements comes to the right side? Kindly explain in detail. > > > > 2008/4/22 Pramod Negi <[EMAIL PROTECTED]>: > > > > > i didnt get what u want to so say (the bold lines) > > > > > > On 4/21/08, Dave <[EMAIL PROTECTED]> wrote: > > > > > > > > > > > Use a divide-and-conquer algorithm to find the median, rearranging > > > > the > > > > array so that the values less than the median precede it in the > > > > array > > > > and the values greater than the median follow it. So the median is > > > > a(n/ > > > > 2).* Now use the divide-and-conquer algorithm twice more to locate > > > > the > > > > (n/2-k)th and (n/2+k)th elements*. Finally, march out both > > > > directions > > > > from n/2, selecting the closest elements to a(n/2). Each of these > > > > operations can be done in O(n), so the total algorithm is O(n). > > > > > > > > Dave > > > > > > > > On Apr 21, 9:35 am, Algo <[EMAIL PROTECTED]> wrote: > > > > > hi this is prob 9-3.7 of CLRS , anybody having a clue??? > > > > > > > > > > Describe an O(n)-time algorithm that, given a set S of n distinct > > > > > numbers and a positive > > > > > integer k ≤ n, determines the k numbers in S that are closest to > > > > the > > > > > median of S > > > > > > > > > > thanks in advance.. > > > > > > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
