Top-N queries in Redis - Time & Space Complexity

Time Complexity: Top-N queries

O(N)

Understanding Time Complexity

When we ask for the top N items in Redis, we want to know how the time to get those items changes as the data grows.

We want to understand how fast Redis can find the top scores or values as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Add scores to a sorted set
ZADD leaderboard 100 "Alice"
ZADD leaderboard 200 "Bob"
ZADD leaderboard 150 "Carol"

# Get top 2 players by score descending
ZREVRANGE leaderboard 0 1 WITHSCORES
    

This code adds players with scores to a sorted set and then retrieves the top 2 players with the highest scores.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Retrieving the top N elements from the sorted set.
• How many times: The operation scans or accesses elements up to N times to return the top N results.

How Execution Grows With Input

Getting the top N items takes time mostly based on N, not the total size of the set.

Input Size (n)	Approx. Operations
10	About 10 operations to get top 10
100	About 10 operations to get top 10
1000	About 10 operations to get top 10

Pattern observation: The time depends on how many top items you want, not on how many total items are in the set.

Final Time Complexity

Time Complexity: O(N)

This means the time to get the top N items grows linearly with N, regardless of the total data size.

Common Mistake

[X] Wrong: "Getting top N items takes longer as the whole set grows bigger."

[OK] Correct: Redis uses a sorted set structure that lets it jump directly to the top scores, so the total size does not slow down fetching the top N.

Interview Connect

Understanding how Redis handles top-N queries shows you know how to work with efficient data structures and can explain performance clearly.

Self-Check

"What if we asked for the bottom N items instead of the top N? How would the time complexity change?"