In a Python list, append(x) and insert(0, x) cost…
Options
- Both are O(1) in the average case
- append: O(1) amortized; insert(0): O(n) (Correct option)
- Both are O(n) since the list is copied
- append: O(n); insert(0): O(1) in CPython
Answer
append O(1) amortized, insert(0, x) O(n)
Why
A Python list is a dynamic array: items sit next to each other in memory.
Adding at the END just uses the next free slot: O(1) (occasionally the array grows, but on average still O(1)).
Inserting at the FRONT means shifting every existing item one place to the right: O(n). Use collections.deque if you need fast front inserts.
Remember
List end = fast. List front = slow.