Also, you can choose not to use a tree here. Just sort the remaining √n elements first, then insert these √n elements sequentially into the n-√n elements' array. The essential here is to store all these elements in a linked list rather than an array, because using an array the program always needs to do a lot of element shifting manipulations which is a time-consuming thing.
On Fri, Aug 27, 2010 at 4:40 AM, Yan Wang <wangyanadam1...@gmail.com> wrote: > We can turn the sorted array with first (n − √n) elements recursively > to a balanced binary sorting tree. This can be done by choosing the > median as the pivot in every step and then recursively manipulate the > left half array and right half array in this way. For a sorted array, > to find its median is an easy action with constant time complexity. > Thus this procedure will cost O(n-√n) time. At last, we insert the > remaining √n elements into the tree, this will cost O(√n * log(n - > √n)) time. So the ultimate time complexity will be O(n). > > On Thu, Aug 26, 2010 at 9:56 PM, Rahul Singal <rahulsinga...@gmail.com> wrote: >> @saurav >> >> I dont think in place approach is possible . This will end up taking n^2 >> time . >> >> -- >> 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. >> > -- 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.
