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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Aug 24 '14 at 16:34
  • $\begingroup$ if i know it, i didnt ask $\endgroup$ – 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.)

  • $\begingroup$ Dear FranW, i know this fact. but in create a recurrence and solve it get stuck. $\endgroup$ – Hamid Kir Aug 24 '14 at 10:56
  • 3
    $\begingroup$ @HamidKir If you know this, why didn't you mention it in the question, so you'd get hints that adress the point, you are struggling with? $\endgroup$ – FrankW Aug 24 '14 at 11:16
  • $\begingroup$ i couldent try to wrote a recurrence relation and solve it. i think it's not need on question. $\endgroup$ – Hamid Kir Aug 24 '14 at 11:31
  • $\begingroup$ Dear @FranW, would you please complete your answeR? $\endgroup$ – Hamid Kir Aug 24 '14 at 16:07
  • 1
    $\begingroup$ @HamidKir Frank is right: your question should include how far you got. For instance, we have reference material on solving recurrences. $\endgroup$ – Raphael Aug 24 '14 at 16:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.