APPEND for string concatenation in Redis - Time & Space Complexity

Time Complexity: APPEND for string concatenation

O(n)

Understanding Time Complexity

We want to understand how the time it takes to add text to a string in Redis changes as the string gets longer.

How does the APPEND command's speed change when the string grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

APPEND mykey "Hello"
APPEND mykey " World"
APPEND mykey "!"
    

This code adds pieces of text to the end of the string stored at key "mykey" step by step.

Identify Repeating Operations

• Primary operation: Adding new text to the end of an existing string.
• How many times: Once per APPEND command, each time the string grows.

How Execution Grows With Input

Each time we add text, Redis must copy the whole existing string plus the new text to create the updated string.

Input Size (n)	Approx. Operations
10	About 10 steps to copy existing text
100	About 100 steps to copy existing text
1000	About 1000 steps to copy existing text

Pattern observation: The work grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to append grows linearly with the length of the string already stored.

Common Mistake

[X] Wrong: "Appending text always takes the same time no matter how long the string is."

[OK] Correct: Because Redis must copy the whole string each time it adds more text, longer strings take more time.

Interview Connect

Understanding how string operations scale helps you explain performance in real applications and shows you can think about efficiency clearly.

Self-Check

"What if Redis used a linked list of strings internally instead of copying the whole string each time? How would the time complexity change?"