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.
[ Parent
| on HN ]
There are no comments on this comment yet.