How do you calculate time complexity for Quicksort?

Answer 1

First, we want to set up a recurrence relation. If we consider the best-case for the quicksort, that is, that each partition splits the collection in 1/2 (not a valid assumption), then (look at a recursive quicksort algorithm):

The partition requires about n comparisons. It is then left to sort 2 collections of size n/2. So:

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

Use repeated substitution, or the "master theorem" or whatever it's called, a generalisation of closed forms, or draw a tree, or use the accounting method, or guess at the answer, prove it by induction.

Now, we need to consider the worst case. The partition still costs the same (about n comparisons), but the partition didn't yield 2 nice-sized sub-collections to sort. Instead, we have a single sub-array to sort, of size n-1 . So now the recurrence relation looks like:

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

Solve this in your favorite way.

Now, on average, how good is your algorithm? That depends on how well you choose your pivot. You can do some reasoning, or, you can run some nice experiments.

Have fun.