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?