Time Complexity: SUNIONSTORE for storing results
O(n)
0
0
SUNIONSTORE for storing results in Redis - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time needed to combine sets grows when using SUNIONSTORE in Redis.
Specifically, how does the work change as the sets get bigger?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
# Combine two sets and store the result
SUNIONSTORE resultSet set1 set2
# Retrieve the combined set
SMEMBERS resultSet
This code takes two sets, merges their unique members into a new set, and stores it under a new key.
Identify Repeating Operations
Look for repeated actions that take time.
- Primary operation: Scanning all members of each input set to combine them.
- How many times: Once for each member in each input set.
How Execution Grows With Input
As the sets get bigger, the work grows roughly with the total number of unique members.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 to 20 operations |
| 100 | About 100 to 200 operations |
| 1000 | About 1000 to 2000 operations |
Pattern observation: The work grows roughly in direct proportion to the total number of elements in the input sets combined.
Final Time Complexity
Time Complexity: O(n)
This means the time to combine sets grows linearly with the total number of elements in all input sets.
Common Mistake
[X] Wrong: "SUNIONSTORE runs instantly no matter how big the sets are."
[OK] Correct: The command must look at every element in the input sets to combine them, so bigger sets take more time.
Interview Connect
Understanding how set operations scale helps you reason about performance in real applications using Redis sets.
Self-Check
"What if we used SUNIONSTORE with three or more sets instead of two? How would the time complexity change?"