LPUSH and RPUSH for insertion in Redis - Time & Space Complexity

Time Complexity: LPUSH and RPUSH for insertion

O(1)

Understanding Time Complexity

When adding items to a list in Redis, it's important to know how the time it takes grows as the list gets bigger.

We want to understand how fast LPUSH and RPUSH commands work as the list grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Add elements to the start of the list
LPUSH mylist "item1"
LPUSH mylist "item2"

# Add elements to the end of the list
RPUSH mylist "item3"
RPUSH mylist "item4"
    

This code adds items to the beginning and end of a Redis list named 'mylist'.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting an element at the start or end of the list.
• How many times: Each LPUSH or RPUSH command inserts one element once.

How Execution Grows With Input

Adding one item to the start or end of the list takes about the same time no matter how big the list is.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time to insert stays roughly the same even as the list grows.

Final Time Complexity

Time Complexity: O(1)

This means inserting an item at the start or end of the list takes constant time, no matter how many items are already in the list.

Common Mistake

[X] Wrong: "Adding items to the start of a list takes longer as the list grows because it has to move all the other items."

[OK] Correct: Redis lists are designed to add items at the start or end quickly without shifting all elements, so the time stays constant.

Interview Connect

Understanding how Redis handles list insertions helps you explain efficient data operations clearly and confidently in real-world situations.

Self-Check

"What if we used the LINSERT command to add an item in the middle of the list? How would the time complexity change?"