Adding and removing list elements in Python - Time & Space Complexity

Time Complexity: Adding and removing list elements

O(n²)

Understanding Time Complexity

When we add or remove items from a list, the time it takes can change depending on how we do it.

We want to understand how the time grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_list = []

# Add elements to the end
for i in range(n):
    my_list.append(i)

# Remove elements from the start
for i in range(n):
    my_list.pop(0)

This code adds n elements to the end of a list, then removes n elements from the start one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding elements at the end with append and removing elements from the start with pop(0).
• How many times: Each operation runs n times in a loop.
• Dominant operation: Removing from the start (pop(0)) because it shifts all remaining elements each time.

How Execution Grows With Input

Adding at the end grows slowly, but removing from the start grows faster as the list gets bigger.

Input Size (n)	Approx. Operations
10	About 10 appends + 55 shifts when popping
100	About 100 appends + 5,050 shifts when popping
1000	About 1000 appends + 500,500 shifts when popping

Pattern observation: Appending grows linearly, but popping from the start grows roughly like the square of n because each pop shifts many elements.

Final Time Complexity

Time Complexity: O(n²)

This means the total time grows roughly like the square of the number of elements when removing from the start repeatedly.

Common Mistake

[X] Wrong: "Removing an element from the start of a list is as fast as removing from the end."

[OK] Correct: Removing from the start makes Python move all the other elements forward, which takes more time as the list grows.

Interview Connect

Understanding how list operations scale helps you choose the right data structure and write efficient code, a skill valued in many coding challenges.

Self-Check

What if we used a deque (double-ended queue) instead of a list for removing elements from the start? How would the time complexity change?