List concatenation and repetition in Python - Time & Space Complexity

Time Complexity: List concatenation and repetition

O(n * k)

Understanding Time Complexity

We want to understand how the time it takes to join or repeat lists changes as the lists get bigger.

How does the work grow when we add or repeat lists of different sizes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

a = [1, 2, 3]
b = [4, 5, 6]
c = a + b * 3

This code joins list a with list b repeated three times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying elements from lists to create a new list.
• How many times: The elements of b are copied 3 times, then elements of a and the repeated b are copied once more to form the final list.

How Execution Grows With Input

When the lists get bigger, the time to copy all elements grows proportionally to their total size.

Input Size (n)	Approx. Operations
10	Copy about 10 + 3*10 = 40 elements
100	Copy about 100 + 3*100 = 400 elements
1000	Copy about 1000 + 3*1000 = 4000 elements

Pattern observation: The work grows linearly with the size of the lists and the repetition count.

Final Time Complexity

Time Complexity: O(n * k)

This means the time grows in proportion to the size of the list b times the repetition count k, plus the size of list a.

Common Mistake

[X] Wrong: "Repeating a list with * is instant and does not depend on list size."

[OK] Correct: Actually, repeating a list creates a new list by copying elements multiple times, so it takes longer as the list or repetition grows.

Interview Connect

Understanding how list operations scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we used list.extend() instead of + for concatenation? How would the time complexity change?"