>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 -- http://mail.python.org/mailman/listinfo/python-list