If you are inserting 3 into an indexed and sorted list (1,2,4,5) you can calculate the index of 3 in O(Log N). But you also need to update the index of 4, and 5 which is an O(N) operation.