for a pivot picked randomly, even the same input array would have different time complexity going through quicksort thousands of thousands of times. the worst case could happen too(but the probability is very small), so random-pivot-set has statistically on average O(logN), we are talking about average on thousands of run, not individual one.
On Saturday, September 15, 2012 2:27:50 PM UTC-4, atul007 wrote: > > typo error :- > we can make it *independent** of this input format > > On Sat, Sep 15, 2012 at 11:56 PM, atul anand <atul.8...@gmail.com<javascript:> > > wrote: > >> pivot position plays important role in determining the time complexity >> of the algorithm. >> suppose array is already sorted then if you go by obvious means by >> selecting pivot element as the 1st element of the input array,then >> recurrence will be :- >> T(n)=T(n-1)+theta(n) >> hence complexity of the algo will be O(n^2). >> actually if you form a recurrence tree you will see that it form like a >> skewed tree , so at every stage you are not dividing the problem into 2 >> parts. >> >> if we are lucky we will have pivot element arnd the center of the >> array,now this will divided the problem into T(n/2)+theta(n) = nlogn. >> >> so suppose you are competing in sorting challenge and me as your opponent >> will give you sorted input so that i can get a plus point over your algo. >> >> so how can we avoid this ?? >> now as we know by now that time complexity is dependent on the input >> format(inc/dec order or nearly sorted).we can make it interdependent of >> this input format by randomizing the input sequence OR we select random >> pivot instead of selecting 1st element as pivot. >> This is know as randomized quick sort.now quicksort will no longer >> dependent on the input sequence but worst case complexity still remain >> O(n^2) , because if your random generator function given input as sorted >> sequence complexity still be O(n^2). >> >> On Sat, Sep 15, 2012 at 7:43 PM, sulekha metta >> <metta....@gmail.com<javascript:> >> > wrote: >> >>> hi every one!! >>> how does pivot position effect the efficiency in quick sort >>> algorithm >>> 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 algo...@googlegroups.com<javascript:> >>> . >>> To unsubscribe from this group, send email to >>> algogeeks+...@googlegroups.com <javascript:>. >>> 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/nDf15aeA4j8J. To post to this group, send email to algogeeks@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.
