I have been given this algorithm that computes the median of an array and partitions the other items around it.

It puts all the elements smaller than the median in a set A1, all those equal to it in A2 and all those bigger in A3. If A1 is bigger than 1 it goes recursively into it and the same happens for A3. It terminates after copying a concatenation of A1, A2 and A3 in A.

I know it’s very similar to Quickselect, but I don’t know how to proceed in order to figure out the time complexity in the worst case.

What I know is that in Quicksort, time complexity is T(n) = n -1 + T(a) + T(n -a-1), where n - 1 is for the partition, T(a) is the recursive call on the first part and t(n-a-1) is the recursive call on the last part. In that case the worst scenario happened when the pivot was always the biggest or the smallest item in the array.

But now, since we have the median as the pivot, what could the worst case be?

1 Answers

Community On

You can use the Big 5 Algorithm which will give you an approximate median. If you use this as your pivot in quicksort, the worst-case complexity would be O(n log n) instead of O(n^2), since we are making equal divisions each time instead of the worst case when we divide unequally with one bucket having one element and the other having n - 1 elements.

This worst case is very unlikely on the other hand. There is a decent amount overhead attached with finding the pivot point using the Big 5 median algorithm, so in practice is it outperformed by choosing random pivots. But if you wanted to find the median every time, the worst case would be O(n logn)