I did not actually run the code, so there may be syntax errors and so forth. But how is L[x] = Y an O(1) operation. Given x finding L[x] would require to traverse x nodes in the list. So finding L[x] requires O(x) time. Once you find L[x] setting it to Y is O(1) I agree.
In Solution B: By L.index(X), I mean search for X and then replace it with Y. Here every time the search starts from the beginning of the list. Hence the inefficiency. - Murali -- http://mail.python.org/mailman/listinfo/python-list