On Fri, Jun 17, 2011 at 3:02 PM, Shashank Singh <shashank.sunny.si...@gmail.com> wrote: > Correct me if I am wrong here but isn't the second one is O(log N)? > Binary search? > That is when you have an already sorted list from somewhere and you > are inserting just one new value.
Finding the position to insert is O(log n), but the actual insert is O(n). This is because Python lists are implemented with arrays and everything after the inserted item has to be moved in memory to make space for the insert. -- http://mail.python.org/mailman/listinfo/python-list
