I know that quicksort with Lomuto's partition method faces worst case run-time $\Theta(n^2)$ when there are many repeating elements in the array.

However, I'm trying to figure out - how many repeating elements are too many?

For example, what if the given array has exactly $n/2$ repeating elements?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.