Time Complexity: Geo-proximity with sorted sets
O(n)
0
0
Geo-proximity with sorted sets in Redis - Time & Space Complexity
Understanding Time Complexity
When we use Redis sorted sets to find nearby locations, we want to know how the time to get results changes as we add more places.
We ask: How does searching for nearby points grow when the list of locations grows?
Scenario Under Consideration
Analyze the time complexity of the following Redis commands.
GEOADD places 13.361389 38.115556 "Palermo"
GEOADD places 15.087269 37.502669 "Catania"
GEORADIUS places 15 37 200 km WITHDIST
This code adds two locations to a sorted set and then finds all places within 200 km of a point.
Identify Repeating Operations
Look for repeated work inside the GEORADIUS command.
- Primary operation: Checking each location's distance to the center point.
- How many times: Once for every location stored in the sorted set.
How Execution Grows With Input
As you add more places, Redis checks each one to see if it fits inside the radius.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 distance checks |
| 100 | About 100 distance checks |
| 1000 | About 1000 distance checks |
Pattern observation: The work grows directly with the number of locations you have.
Final Time Complexity
Time Complexity: O(n)
This means the time to find nearby places grows in a straight line with how many places you store.
Common Mistake
[X] Wrong: "Redis finds nearby places instantly no matter how many locations there are."
[OK] Correct: Redis must check each location's distance, so more places mean more work and more time.
Interview Connect
Understanding how Redis handles geo queries helps you explain how data size affects speed in real apps.
This skill shows you can think about performance, not just code.
Self-Check
"What if Redis used a spatial index to reduce the number of distance checks? How would the time complexity change?"