Abuse of Big Oh notation
no.email at nospam.invalid
Mon Aug 20 01:42:03 CEST 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 but never ask for string". 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