Efficient Find and Replace

[bearophileHUGS at lycos.com]

>Because L.index() and L[x:x] both take O(N) time in the worst case.

Why do you think L[x:x] can be O(N)?

This looks O-linear enough to me:

>>> from random import choice
>>> L = [choice("ab") for i in xrange(10)]
>>> L
['b', 'b', 'b', 'a', 'b', 'a', 'b', 'a', 'a', 'a']
>>> for x in xrange(len(L)):
... 	if L[x] == "a": L[x] = "c"
>>> L
['b', 'b', 'b', 'c', 'b', 'c', 'b', 'c', 'c', 'c']

Bye,
bearophile