# Quicksort's asymptotic performance for array of [50,…,50,100,…100]

Let's have an array where first half are of value 50 and the second half 100. What would be the asymptotic performance when sorting using Quicksort.

I think it it should be $O(n^2)$ as for array of same elements the complexity is $O(n^2)$ and this particular problem could be rewritten as sorting the first half + sorting the second hald $O(2*(\frac{n}{2})^2 + n)$ which is still $O(n^2)$.

But my schoolmates claim it should be $O(n log(n))$.. so which one is correct?

• The behaviour of Quicksort on inputs with duplicates depends on the specifics of the implementation. Which one are you investigating? – Raphael Jan 12 '14 at 21:49

We can observe the input array given to the algorithm is already sorted. So at each step, the array is partitioned into two subarrays of size $n-1$ and 0 (why?). This gives us the recurrence $T(n) = T(n-1) + T(0) + \Theta(n)$. Can you now bound $T(n)$, and answer your question?