On Fri, 27 Jan 2006 16:34:53 -0800, Murali wrote: > 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.
You are assuming that Python lists are linked lists. They are not. They are arrays. Accessing the entry at position x doesn't require traversing the list at all. > 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. Yes, but the inefficient search code is done in C, which is so fast that it really doesn't matter unless your list is HUGE. -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
