algorithm complexity of quicksort?

Question

I have found the following quicksort algorithm:

function quicksort(array)
    less, equal, greater := three empty arrays
    if length(array) > 1  
        pivot := select any element of array
        for each x in array
            if x < pivot then add x to less
            if x = pivot then add x to equal
            if x > pivot then add x to greater
        quicksort(less)
        quicksort(greater)
        array := concatenate(less, equal, greater)

and I want to make its algorithm analysis by finding the recurrence relation. For what I see everytime that this algorithm is called, by choosing the pivot, for example, in the first position of the original array. It calls the quicksort again with the two generated lists, so I will have:

                   one list ------ pow(2,0)=1
                less       greater--------2 lists----pow(2,1)=2
   less greater              less greater-------4 lists---pow(2,2)=4

so it seems it forms a sort of binary tree, so if I get the pattern it will be: 2^k=n, where k is the levels of recursion, so I will have O(log n)

but how to do the same with analysis of recurrences? I mean, because I am not calculating the process of the de-stack of the function, something that happens in all recursive algorithms.

Any help? Thanks

igon · Accepted Answer · 2014-10-21 14:00:32Z

1

First of all you should consider Quicksort is not deterministic. So you should make an analysis for the worst case - best case - average case.

In the worst case as an example:

T(n) = T(n-1) + O(n)

The O(n) comes from the fact that you are partitioning the whole array. The T(n-1) instead is the number of elements left to partition in the worst case.

If you solve the recurrence using the master theorem you'll get O(n^2)

Similarly in the best case:

T(n) = 2T(n/2) + O(n)

This is the same as merge-sort and again applying the master theorem you get O(nlogn).

answered Oct 21, 2014 at 14:00

igon

3,0661 gold badge25 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Prasanna Over a year ago

Can you please elaborate with the master theorem on how are you able to get O(n^2) complexity?

UniversE · Accepted Answer · 2021-03-01 20:54:17Z

0

I think it's the master theorem you are looking for.

And here is an analysis of quicksort using that theorem: https://stackoverflow.com/a/40308659/2534472

edited Mar 1, 2021 at 20:54

answered Oct 21, 2014 at 14:00

UniversE

2,51620 silver badges30 bronze badges

1 Comment

UniversE Over a year ago

@Prasanna done. I linked another SO answer now, that is very unlikely to be removed in the future. Thanks :)

Collectives™ on Stack Overflow

algorithm complexity of quicksort?

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related