Time Complexity: Range queries for scoring
O(log n + m)
0
0
Range queries for scoring in Redis - Time & Space Complexity
Understanding Time Complexity
When we ask Redis to find items within a score range, we want to know how the time it takes grows as more items are stored.
We are trying to see how the cost changes when the number of scored items increases.
Scenario Under Consideration
Analyze the time complexity of the following Redis commands.
ZADD leaderboard 100 user1
ZADD leaderboard 200 user2
ZADD leaderboard 300 user3
ZRANGEBYSCORE leaderboard 150 350
This code adds users with scores to a sorted set and then queries users with scores between 150 and 350.
Identify Repeating Operations
Look for repeated work inside the query.
- Primary operation: Redis scans the sorted set to find members with scores in the given range.
- How many times: It depends on how many items fall inside the score range.
How Execution Grows With Input
As the total number of items grows, the time to find items in a score range grows mostly with how many items match the range.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About number of items in range (e.g., 3) |
| 100 | About number of items in range (e.g., 20) |
| 1000 | About number of items in range (e.g., 150) |
Pattern observation: The work grows with how many items are returned, not the total stored.
Final Time Complexity
Time Complexity: O(log n + m)
This means Redis quickly finds the start point with a small cost, then spends time proportional to how many items match the score range.
Common Mistake
[X] Wrong: "The query time grows only with the total number of items stored."
[OK] Correct: Redis uses a fast search to jump to the start of the range, so the main cost depends on how many items are in the range, not all items.
Interview Connect
Understanding how range queries scale helps you explain how databases handle large data efficiently, a useful skill in many real-world projects.
Self-Check
"What if we asked for a range that includes almost all items? How would the time complexity change?"