Accessing keys and arguments in Redis - Time & Space Complexity

Time Complexity: Accessing keys and arguments

O(n)

Understanding Time Complexity

When working with Redis commands, it is important to understand how the time to access keys and arguments changes as the number of keys or arguments grows.

We want to know how the cost of accessing these keys and arguments grows when we have more of them.

Scenario Under Consideration

Analyze the time complexity of the following Redis Lua script snippet.

-- Access keys and arguments in a Redis Lua script
local key1 = KEYS[1]
local key2 = KEYS[2]
local arg1 = ARGV[1]
local arg2 = ARGV[2]

redis.call('SET', key1, arg1)
redis.call('SET', key2, arg2)
    

This script accesses two keys and two arguments, then sets values for those keys using the arguments.

Identify Repeating Operations

Look for repeated actions that take time as input grows.

• Primary operation: Accessing each key and argument once.
• How many times: Once per key and once per argument; no loops here.

How Execution Grows With Input

As the number of keys and arguments increases, the number of accesses grows directly with them.

Input Size (n keys + n args)	Approx. Operations
10	About 10 key accesses + 10 argument accesses = 20 operations
100	About 100 key accesses + 100 argument accesses = 200 operations
1000	About 1000 key accesses + 1000 argument accesses = 2000 operations

Pattern observation: The work grows in a straight line as the number of keys and arguments increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to access keys and arguments grows directly in proportion to how many there are.

Common Mistake

[X] Wrong: "Accessing keys and arguments is always constant time, no matter how many there are."

[OK] Correct: Each key and argument must be accessed individually, so more keys or arguments mean more work.

Interview Connect

Understanding how accessing keys and arguments scales helps you write efficient Redis scripts and shows you can think about performance clearly.

Self-Check

"What if the script used a loop to access keys instead of accessing them one by one? How would the time complexity change?"