Time Complexity: DISCARD to abort
O(n)
0
0
DISCARD to abort in Redis - Time & Space Complexity
Understanding Time Complexity
When using Redis transactions, it's important to know how the time cost changes when you abort a transaction with DISCARD.
We want to understand how DISCARD affects the work Redis does as the transaction size grows.
Scenario Under Consideration
Analyze the time complexity of the following Redis transaction with DISCARD.
MULTI
SET key1 value1
SET key2 value2
... (more commands) ...
DISCARD
This code starts a transaction, queues several commands, then aborts all queued commands using DISCARD.
Identify Repeating Operations
Look for repeated actions inside the transaction before DISCARD.
- Primary operation: Queuing each command inside the transaction.
- How many times: Once per command queued before DISCARD.
How Execution Grows With Input
As you add more commands before DISCARD, Redis queues more commands.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | Queue 10 commands, then DISCARD clears all |
| 100 | Queue 100 commands, then DISCARD clears all |
| 1000 | Queue 1000 commands, then DISCARD clears all |
Pattern observation: The work to queue commands grows with the number of commands, but DISCARD clears all queued commands in a single step.
Final Time Complexity
Time Complexity: O(n)
This means the time to abort with DISCARD grows linearly with the number of commands queued in the transaction.
Common Mistake
[X] Wrong: "DISCARD instantly cancels the transaction with no extra work regardless of size."
[OK] Correct: Redis must clear all queued commands, so the time depends on how many commands were queued before DISCARD.
Interview Connect
Understanding how DISCARD works helps you reason about transaction costs and error handling in Redis, a useful skill for real-world database tasks.
Self-Check
"What if we replaced DISCARD with EXEC? How would the time complexity change?"