Time Complexity: GETRANGE and SETRANGE
O(n)
0
0
GETRANGE and SETRANGE in Redis - Time & Space Complexity
Understanding Time Complexity
When working with strings in Redis, it's important to know how fast operations like GETRANGE and SETRANGE run.
We want to understand how the time to get or set parts of a string changes as the string grows.
Scenario Under Consideration
Analyze the time complexity of the following Redis commands.
# Get part of a string from start to end index
GETRANGE mykey 0 99
# Set part of a string starting at offset
SETRANGE mykey 50 "hello"
GETRANGE reads a substring from a stored string. SETRANGE overwrites part of the string starting at a given position.
Identify Repeating Operations
Both commands work by accessing a part of the string stored in Redis.
- Primary operation: Reading or writing a segment of the string.
- How many times: The operation depends on the length of the substring accessed or modified.
How Execution Grows With Input
The time to get or set a substring grows with the length of that substring, not the whole string.
| Substring Length (n) | Approx. Operations |
|---|---|
| 10 | About 10 steps |
| 100 | About 100 steps |
| 1000 | About 1000 steps |
Pattern observation: The work grows linearly with the substring length you access or modify.
Final Time Complexity
Time Complexity: O(n)
This means the time to get or set part of a string grows directly with the size of that part.
Common Mistake
[X] Wrong: "GETRANGE and SETRANGE always run in constant time regardless of substring size."
[OK] Correct: Actually, these commands must process each character in the substring, so bigger substrings take more time.
Interview Connect
Understanding how substring operations scale helps you reason about performance in real Redis use cases.
Self-Check
"What if we used SETRANGE to overwrite the entire string instead of a part? How would the time complexity change?"