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

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.