2

Is there a difference between append and insert at the end of a list? Is insert at the end of a list a constant time operation?

nums = [1, 2, 3]
nums.append(4)  # Time complexity: O(1)
nums.insert(len(nums), 5)  # Time complexity: O(?)

According to the TimeComplexity article in the Python Wiki, the average case for append is O(1), while the average case for insert is O(n). However, in the Python tutorial, it is mentioned that:

... and a.insert(len(a), x) is equivalent to a.append(x).

I'm unsure if "equivalent" there means "equivalent in functionality" or "equivalent in time complexity". Does anyone know?

Flux
  • 9,805
  • 5
  • 46
  • 92
  • 1
    timecomplexity article is correct for the general case, because `insert` isnt always just at the end of list. – Paritosh Singh Feb 04 '20 at 04:54
  • @ParitoshSingh Yes I know. My question is whether or not the time complexity for `insert` is O(1) in the special case of inserting at the end of the list. – Flux Feb 04 '20 at 04:56
  • The `n` in insert is effectively the number of elements that needed to be moved. If no elements need to be moved that operation can be ignored. In any case it will still be a time complexity of O(n) simply because the big O notation don't actually measure some vague or even exact time complexity, it's more to describe how their running time/space requirements grow as input size grow. [More details at wikipedia](https://en.wikipedia.org/wiki/Big_O_notation). – metatoaster Feb 04 '20 at 05:09
  • 1
    In other words, `list.insert` is always O(n) on average, and that the big-O notation don't make specific addressing of edge cases (such as the best or worst case scenario; in your case, an operational that can be reduced to a simple `list.append`). – metatoaster Feb 04 '20 at 05:12
  • 1
    Even more pedantically, `append` is amortized O(1), not actually O(1). See [this thread](https://stackoverflow.com/questions/33044883/why-is-the-time-complexity-of-pythons-list-append-method-o1) – metatoaster Feb 04 '20 at 05:17

2 Answers2

3

Worst time complexity for inserting into list is O(n-i), where n is the length of the list and i is the index at which you are inserting.

So in case if you are inserting at the last index, that makes it O(1).

Here is an article that might help you understand better :

https://yourbasic.org/algorithms/time-complexity-arrays/.

Prashant Kumar
  • 2,057
  • 2
  • 9
  • 22
3

Regarding "equivalent in functionality", I'd say it is true since both of them will produce the exact same results for Python lists.

Time-complexity wise it is pretty much equivalent for list under such case, since the list insert() implementation works by shifting the elements behind the index, thus if the new element is inserted at the end of the list, no shifting operations is performed. This can be verified by looking at the implementation of the list insert. In the insertion implementation line 248-251,

for (i = n; --i >= where; )
        items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;

Meanwhile, in the implementation of list append

Py_INCREF(v);
PyList_SET_ITEM(self, n, v);

where the PyList_SET_ITEM is defined as:

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))

Thus, since where equals n, which is the list size in this case, the for loop is terminated right away. Few lines after that are pretty much equivalent, which is basically just inserting the element into the array.

Hence, it can be said that for this case the amortized time complexity is the same, which is O(1)

Hans Tananda
  • 169
  • 8