Steven D'Aprano <steve+comp.lang.pyt...@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. -- http://mail.python.org/mailman/listinfo/python-list
