News for hackers. Stuff that matters.
Re:Faster string searching and matching with Rabin-Karp algo... by ahelwer on Saturday April 07, 2012 @12:55PM (#3811304)
Hmm? Expected running time is a valid and important concept. In Quicksort, for example, picking the pivot element randomly results in O(n^2) runtime in the worst case, but has an expected runtime of O(n log(n)). The O(n log(n)) limit can be enforced using the median-of-medians method for pivot selection, but that's a pain to program and has a much higher constant factor than generating a random number; the only benefit being theoretical computer scientists sleep well at night.

There are no comments on this comment yet.