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?"

Practice

1. What does the expression [1, 2] + [3, 4] do in Python?

easy

A. Creates a new list combining both lists: [1, 2, 3, 4]

B. Repeats the first list twice: [1, 2, 1, 2]

C. Creates a list of two lists: [[1, 2], [3, 4]]

D. Raises a TypeError because lists cannot be added

Solution

1. Step 1: Understand the + operator with lists

   The + operator joins two lists into one new list containing all elements from both.

2. Step 2: Apply + to [1, 2] and [3, 4]

   Joining these lists results in [1, 2, 3, 4].

3. Final Answer:

   Creates a new list combining both lists: [1, 2, 3, 4] -> Option A

4. Quick Check:

   List concatenation = combined list [OK]

Hint: Use + to join lists, not to repeat [OK]

Common Mistakes:

• Thinking + repeats lists instead of joining
• Confusing list concatenation with nesting
• Expecting an error when adding lists

2. Which of the following is the correct syntax to repeat the list [5, 6] three times?

easy

A. [5, 6] ** 3

B. [5, 6] + 3

C. 3 + [5, 6]

D. [5, 6] * 3

Solution

1. Step 1: Identify the operator for repetition

   The * operator repeats a list multiple times when used with an integer.

2. Step 2: Check syntax correctness

   [5, 6] * 3 repeats the list three times: [5, 6, 5, 6, 5, 6].

3. Final Answer:

   [5, 6] * 3 -> Option D

4. Quick Check:

   List repetition uses * operator [OK]

Hint: Use * with list and number to repeat [OK]

Common Mistakes:

• Using + instead of * for repetition
• Trying to use ** which is invalid for lists
• Confusing order of operands for repetition

3. What is the output of this code?

lst1 = [1]
lst2 = [2, 3]
result = lst1 * 2 + lst2 * 3
print(result)

medium

A. [1, 1, 2, 3, 2, 3, 2, 3]

B. [1, 2, 3, 1, 2, 3]

C. [1, 1, 2, 3, 3, 3]

D. [1, 1, 2, 3, 2, 3]

Solution

1. Step 1: Calculate lst1 * 2

   Repeating [1] twice gives [1, 1].

2. Step 2: Calculate lst2 * 3

   Repeating [2, 3] three times gives [2, 3, 2, 3, 2, 3].

3. Step 3: Concatenate the two results

   Adding [1, 1] + [2, 3, 2, 3, 2, 3] results in [1, 1, 2, 3, 2, 3, 2, 3].

4. Final Answer:

   [1, 1, 2, 3, 2, 3, 2, 3] -> Option A

5. Quick Check:

   Repeat then join lists = combined repeated list [OK]

Hint: Repeat lists first, then add them [OK]

Common Mistakes:

• Adding before repeating
• Miscounting repeated elements
• Confusing order of concatenation

4. Find the error in this code snippet:

list_a = [1, 2]
list_b = [3, 4]
result = list_a * list_b
print(result)

medium

A. No error, prints [1, 2, 3, 4]

B. SyntaxError due to missing parentheses

C. TypeError because * expects an integer, not a list

D. ValueError because lists cannot be multiplied

Solution

1. Step 1: Understand list repetition rules

   List repetition uses * with an integer, not another list.

2. Step 2: Identify the error in list_a * list_b

   Multiplying two lists causes a TypeError because the right operand must be int.

3. Final Answer:

   TypeError because * expects an integer, not a list -> Option C

4. Quick Check:

   List * list is invalid, needs int [OK]

Hint: Right side of * must be integer for list repetition [OK]

Common Mistakes:

• Trying to multiply two lists directly
• Expecting concatenation with * operator
• Confusing syntax error with type error

5. You have two lists:
fruits = ['apple', 'banana']
veggies = ['carrot']
How do you create a new list that repeats the fruits twice and veggies three times, then combines them all in order?

hard

A. fruits * veggies * 5

B. fruits * 2 + veggies * 3

C. fruits + veggies * 5

D. (fruits + veggies) * 5

Solution

1. Step 1: Repeat fruits and veggies separately

   fruits * 2 repeats fruits twice; veggies * 3 repeats veggies three times.

2. Step 2: Concatenate the repeated lists

   Adding these repeated lists combines them in order as desired.

3. Final Answer:

   fruits * 2 + veggies * 3 -> Option B

4. Quick Check:

   Repeat separately then add lists [OK]

Hint: Repeat lists separately, then add [OK]

Common Mistakes:

• Repeating combined list instead of separate lists
• Using invalid multiplication of lists
• Confusing order of operations