List vs sorted set for sequences in Redis - Performance Comparison

Time Complexity: List vs sorted set for sequences

O(1) for LPUSH, O(k) for LRANGE, O(n) for LREM; O(log n) for ZADD, ZREM, and O(k) for ZRANGE

Understanding Time Complexity

When using Redis to store sequences, it is important to know how fast operations grow as the sequence gets bigger.

We want to see how the time to add, access, or remove items changes with the size of the sequence.

Scenario Under Consideration

Analyze the time complexity of these Redis commands for lists and sorted sets.

# Using a List
LPUSH mylist value
LRANGE mylist 0 9
LREM mylist 1 value

# Using a Sorted Set
ZADD myzset 1 value
ZRANGE myzset 0 9
ZREM myzset value
    

This code adds, reads, and removes items from a list and a sorted set, which are two ways to store sequences in Redis.

Identify Repeating Operations

Look at what repeats when these commands run.

• Primary operation: Adding, reading, and removing items from the data structure.
• How many times: Each command works on the sequence size, which can be many items.

How Execution Grows With Input

As the sequence grows, the time to do these operations changes differently for lists and sorted sets.

Input Size (n)	List Operations	Sorted Set Operations
10	Fast for push and range, slow for remove	Fast for add, range, and remove
100	Push and range still fast, remove slower	All operations remain efficient
1000	Remove becomes noticeably slower	Operations scale well

Lists are quick to add and read from the start but removing items can take longer as the list grows. Sorted sets keep operations fast even as size grows.

Final Time Complexity

Time Complexity: O(1) for LPUSH, O(k) for LRANGE, O(n) for LREM; O(log n) for ZADD, ZREM, and O(k) for ZRANGE

This means lists are very fast to add at the front and read ranges, but removing items can take longer as the list grows. Sorted sets keep add, remove, and range operations efficient even with large sequences.

Common Mistake

[X] Wrong: "Lists and sorted sets have the same speed for all operations because they both store sequences."

[OK] Correct: Lists are simple sequences with fast push/pop at ends but slow removal inside. Sorted sets use a tree structure that keeps operations like add and remove faster even as size grows.

Interview Connect

Understanding how Redis data structures behave as data grows shows you can choose the right tool for the job. This skill helps you design fast and scalable systems.

Self-Check

What if we changed the sorted set scores to be random instead of ordered? How would that affect the time complexity of range queries?