Array modification (push, pop, shift, unshift) in Ruby - Time & Space Complexity

Time Complexity: Array modification (push, pop, shift, unshift)

O(1) for push/pop, O(n) for shift/unshift

Understanding Time Complexity

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

We want to know how the work grows when we use push, pop, shift, or unshift on arrays.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

arr = []
arr.push(10)      # Add item at the end
arr.pop           # Remove item from the end
arr.unshift(5)    # Add item at the start
arr.shift         # Remove item from the start
    

This code shows adding and removing items at both ends of an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing one item at either end of the array.
• How many times: Each operation happens once, but internally some may move many items.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations for push/pop	Approx. Operations for shift/unshift
10	1 (simple add/remove)	10 (move all items)
100	1 (simple add/remove)	100 (move all items)
1000	1 (simple add/remove)	1000 (move all items)

Pattern observation: push and pop take about the same small time no matter the size, but shift and unshift take longer as the array grows.

Final Time Complexity

Time Complexity: O(1) for push/pop, O(n) for shift/unshift

This means adding or removing at the end is fast and steady, but doing it at the start gets slower as the array gets bigger.

Common Mistake

[X] Wrong: "All array add/remove operations take the same time."

[OK] Correct: Adding or removing at the start needs to move all other items, so it takes longer when the array is big.

Interview Connect

Understanding these differences helps you explain why some array operations are faster, showing you know how data structures work behind the scenes.

Self-Check

"What if we used a linked list instead of an array? How would the time complexity for adding or removing at the start change?"