# Quick Sort Algorithm When Partition is Constant Time

I ran into a question about Quick Sort Algorithm.

Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of Randomized-Quick Sort?

any hint or solution highly appreciated.

• What have you tried and where did you get stuck? Have you read and understood the "normal" Quicksort analysis? What happens if you replace the "normal" partitioning cost with something else? – Raphael Aug 24 '14 at 16:34
• if i know it, i didnt ask – Hamid Kir Aug 24 '14 at 18:38

Hint: Since the runtime for each recursive call is dominated by the runtime of partition, the runtime of your modified algorithm will be $C$ times the total number of recursive calls. The latter number is independent of the input and relatively easy to determine, by looking at the elements that are not taken into the recursive calls. (Trying to solve this via a recurrence relation is significantly harder.)