News for hackers. Stuff that matters.
Re:Helping a stranger, and why you should understand NP-comp... by eru on Monday November 04, 2013 @02:05PM (#6670447)
Randomized QuickSort has an expected worst case runtime of O(n log n).

To pick that part, first you write your (randomized) QuickSort, then your antagonists picks the worst case, and last you let your algorithm run and pick its random numbers. No matter how the antagonist chooses the input (but not the random numbers), you get O (n log n) expected runtime.

This is different from an average (over all inputs) run time.

There are no comments on this comment yet.