List mutability in Python - Time & Space Complexity

Time Complexity: List mutability

O(1)

Understanding Time Complexity

When we change items in a list, it's important to know how long these changes take as the list grows.

We want to understand how the time to update a list item changes when the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_list = [0] * n
my_list[5] = 10

This code creates a list of size n and then changes the value at index 5.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Direct access and update of a list element by index.
• How many times: Exactly once in this example.

How Execution Grows With Input

Changing one item in a list takes the same amount of time no matter how big the list is.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time stays the same even if the list grows larger.

Final Time Complexity

Time Complexity: O(1)

This means updating a list item by its position takes a constant amount of time, no matter the list size.

Common Mistake

[X] Wrong: "Changing an item in a list takes longer if the list is bigger."

[OK] Correct: Because lists in Python allow direct access by index, the update happens immediately without checking other items.

Interview Connect

Knowing that list updates are quick helps you explain why some operations are fast and others slower, showing you understand how data structures work.

Self-Check

"What if we insert an item at the start of the list? How would the time complexity change?"

Practice

1. Which of the following statements about Python lists is true?

easy

A. Lists cannot be changed once created.

B. Lists can be changed after they are created.

C. Lists are immutable like strings.

D. Lists can only store numbers.

Solution

1. Step 1: Understand list mutability

   Python lists are mutable, meaning you can change their contents after creation.

2. Step 2: Compare options

   Lists can be changed after they are created. ("Lists can be changed after they are created.") correctly states that lists are mutable. Options A and C incorrectly claim lists cannot be changed or are immutable like strings. Lists can only store numbers. is wrong because lists can store any data type.

3. Final Answer:

   Lists can be changed after they are created. -> Option B

4. Quick Check:

   List mutability = True [OK]

Hint: Remember: lists are like clay, easy to reshape [OK]

Common Mistakes:

• Confusing lists with strings (immutable)
• Thinking lists only hold numbers
• Believing lists cannot be changed

2. Which of the following is the correct way to change the first item of a list my_list to 10?

easy

A. my_list[0] = 10

B. my_list(0) = 10

C. my_list{0} = 10

D. my_list.set(0, 10)

Solution

1. Step 1: Recall list item assignment syntax

   In Python, list items are accessed and assigned using square brackets and index, like my_list[0].

2. Step 2: Check each option

   my_list[0] = 10 uses correct syntax. Options B and C use wrong brackets. my_list.set(0, 10) uses a method that does not exist for lists.

3. Final Answer:

   my_list[0] = 10 -> Option A

4. Quick Check:

   Use square brackets for list item assignment [OK]

Hint: Use square brackets [] to access or change list items [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Trying to use curly braces for indexing
• Assuming lists have a set() method

3. What will be the output of this code?

numbers = [1, 2, 3]
numbers[1] = 5
print(numbers)

medium

A. [1, 5, 3]

B. [1, 2, 3]

C. [5, 2, 3]

D. Error

Solution

1. Step 1: Understand list item update

   The code changes the item at index 1 (second item) from 2 to 5.

2. Step 2: Check the final list

   After update, the list becomes [1, 5, 3]. The print statement outputs this list.

3. Final Answer:

   [1, 5, 3] -> Option A

4. Quick Check:

   Updated list = [1, 5, 3] [OK]

Hint: Index 1 means second item in list [OK]

Common Mistakes:

• Thinking index 1 is first item
• Expecting original list unchanged
• Assuming code causes error

4. Find the error in this code that tries to change a list item:

my_list = [10, 20, 30]
my_list(1) = 15
print(my_list)

medium

A. Missing colon after assignment

B. List cannot be changed after creation

C. Using parentheses instead of square brackets for indexing

D. print statement syntax error

Solution

1. Step 1: Identify indexing syntax error

   The code uses parentheses () instead of square brackets [] to access list item.

2. Step 2: Confirm correct syntax

   List items must be accessed with square brackets, so my_list[1] = 15 is correct.

3. Final Answer:

   Using parentheses instead of square brackets for indexing -> Option C

4. Quick Check:

   Use [] not () for list indexing [OK]

Hint: Remember: () calls functions, [] accesses list items [OK]

Common Mistakes:

• Using () instead of [] for list indexing
• Thinking lists are immutable
• Looking for syntax errors elsewhere

5. Given the list data = [5, 10, 15, 20], which code snippet correctly doubles each item in the list using mutability?

hard

A. data = [item * 2 for item in data]
print(data)

B. for item in data:
item = item * 2
print(data)

C. data.map(lambda x: x*2)
print(data)

D. for i in range(len(data)):
data[i] = data[i] * 2
print(data)

Solution

1. Step 1: Understand mutability and iteration

   To change items in place, we must assign new values to each index in the list.

2. Step 2: Analyze each option

   for i in range(len(data)): data[i] = data[i] * 2 print(data) updates each item by index, correctly doubling values in place.
   for item in data: item = item * 2 print(data) changes only the loop variable, not the list.
   data = [item * 2 for item in data] print(data) creates a new list and assigns it to data (not in-place mutation).
   data.map(lambda x: x*2) print(data) uses map which returns an iterator and does not modify list in place.

3. Final Answer:

   for i in range(len(data)): data[i] = data[i] * 2 print(data) -> Option D

4. Quick Check:

   In-place update requires index assignment [OK]

Hint: Use index to update list items for true mutability [OK]

Common Mistakes:

• Modifying loop variable instead of list items
• Using map without converting result
• Replacing list instead of mutating it