News for hackers. Stuff that matters.
Re:New string search algorithm by pjscott on Friday February 11, 2011 @07:50PM (#2208866)
To say that something runs in amortized O(n) time guarantees an upper bound on the average time per operation in a worst-case sequence of operations. It does not deal with average-case time on random or typical data.
Re:New string search algorithm by mayank on Friday February 11, 2011 @07:54PM (#2208876)
I didn't say it did. On the other hand, unless the author of the algorithm is really clueless (edit: or knowingly making a probabilistic statement), I'm sure he meant amortized time.