Lua script syntax in Redis - Time & Space Complexity

Time Complexity: Lua script syntax in Redis

O(n)

Understanding Time Complexity

When running Lua scripts in Redis, it's important to know how the time taken grows as the script processes more data.

We want to understand how the script's execution time changes when the input size changes.

Scenario Under Consideration

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

local key = KEYS[1]
local count = tonumber(ARGV[1])
for i = 1, count do
  redis.call('LPUSH', key, i)
end
return redis.call('LLEN', key)
    

This script pushes numbers from 1 to count into a Redis list and then returns the list length.

Identify Repeating Operations

Look for repeated actions in the script.

• Primary operation: The loop runs redis.call('LPUSH') repeatedly.
• How many times: Exactly count times, once for each number pushed.

How Execution Grows With Input

As the count grows, the number of push operations grows the same way.

Input Size (count)	Approx. Operations
10	10 LPUSH calls + 1 LLEN call
100	100 LPUSH calls + 1 LLEN call
1000	1000 LPUSH calls + 1 LLEN call

Pattern observation: The number of operations grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the script takes longer roughly in direct proportion to how many items it processes.

Common Mistake

[X] Wrong: "The script runs in constant time no matter how many items are pushed."

[OK] Correct: Each LPUSH call adds work, so more items mean more time.

Interview Connect

Understanding how Lua scripts scale in Redis helps you write efficient scripts and explain their performance clearly.

Self-Check

"What if the script used RPUSH instead of LPUSH? How would the time complexity change?"