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.
