Home Original page

Abuse of Big Oh notation

Paul Rubin no.email at nospam.invalid
Sun Aug 19 19:42:03 EDT 2012 
Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:
> Of course *if* k is constant, O(k) is constant too, but k is not 
> constant. In context we are talking about string indexing and slicing. 
> There is no value of k, say, k = 2, for which you can say "People will 
> sometimes ask for string[2] but never ask for string[3]". That is absurd.

The context was parsing, e.g. recognizing a token like "a" or "foo" in a
human-written chunk of text.  Occasionally it might be "sesquipidalian"
or some even worse outlier, but one can reasonably put a fixed and
relatively small upper bound on the expected value of k.  That makes the
amortized complexity O(1), I think.
More information about the Python-list mailing list