News for hackers. Stuff that matters.
Re:New string search algorithm by mayank on Friday February 11, 2011 @07:41PM (#2208837)
> Big O notation refers to boundary times.

No it doesn't. You can have an O(N) amortized time. Big-O is a bounding function up to a constant factor, not necessarily a boundary (as in worst-case) time.

http://en.wikipedia.org/wiki/Amortized_analysis

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.
Re:New string search algorithm by leif on Saturday February 12, 2011 @12:51PM (#2210558)
This is not an amortized analysis, it is a probabilistic analysis.