Nested lists in Python - Time & Space Complexity

Time Complexity: Nested lists

O(n)

Understanding Time Complexity

When working with nested lists, it is important to understand how the time to process them grows as the lists get bigger.

We want to know how the number of steps changes when we look inside lists within lists.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

nested = [[1, 2, 3], [4, 5], [6, 7, 8, 9]]
for inner_list in nested:
    for item in inner_list:
        print(item)

This code goes through each small list inside a bigger list and prints every item.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop that visits each item in every small list.
• How many times: Once for each item inside all the nested lists combined.

How Execution Grows With Input

As the total number of items inside all nested lists grows, the time to print them grows roughly the same way.

Input Size (total items)	Approx. Operations
10	About 10 prints
100	About 100 prints
1000	About 1000 prints

Pattern observation: The time grows directly with the total number of items inside all nested lists.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in a straight line with the total number of items inside the nested lists.

Common Mistake

[X] Wrong: "Because there are two loops, the time must be squared, like O(n²)."

[OK] Correct: The inner loop runs over smaller lists whose total items add up to n, so the loops together still visit each item once, not n times n.

Interview Connect

Understanding how nested lists affect time helps you explain your code clearly and shows you can think about how programs grow with data size.

Self-Check

"What if the inner lists were replaced by dictionaries? How would the time complexity change when iterating over all items?"

Practice

1. What is a nested list in Python?

easy

A. A list with only one element

B. A list that contains other lists as its elements

C. A list that cannot be changed

D. A list that stores only numbers

Solution

1. Step 1: Understand list elements

   A list can hold many types of elements, including other lists.

2. Step 2: Define nested list

   A nested list is a list where some elements are themselves lists.

3. Final Answer:

   A list that contains other lists as its elements -> Option B

4. Quick Check:

   Nested list = list inside list [OK]

Hint: Think of a list inside another list [OK]

Common Mistakes:

• Confusing nested list with single-level list
• Thinking nested list is immutable
• Assuming nested list holds only numbers

2. Which of the following is the correct syntax to create a nested list with two inner lists?

easy

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

B. [1, 2, 3, 4]

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

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

Solution

1. Step 1: Identify nested list syntax

   A nested list has lists inside the main list, each enclosed in brackets.

2. Step 2: Check options

   [[1, 2], [3, 4]] has two inner lists: [1, 2] and [3, 4], correctly nested.

3. Final Answer:

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

4. Quick Check:

   Two inner lists = double brackets [OK]

Hint: Look for double brackets for nested lists [OK]

Common Mistakes:

• Using single brackets only
• Mixing elements and lists incorrectly
• Missing commas between inner lists

3. What is the output of the following code?

matrix = [[1, 2], [3, 4]]
print(matrix[1][0])

medium

A. 3

B. 1

C. 4

D. 2

Solution

1. Step 1: Access outer list element

   matrix[1] accesses the second inner list: [3, 4].

2. Step 2: Access inner list element

   matrix[1][0] accesses the first element of [3, 4], which is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   matrix[1][0] = 3 [OK]

Hint: First index outer list, second index inner list [OK]

Common Mistakes:

• Mixing up indexes (using [0][1] instead)
• Forgetting zero-based indexing
• Confusing inner and outer list positions

4. Find the error in this code snippet:

data = [[1, 2], [3, 4]]
print(data[2][0])

medium

A. No error, output is 3

B. SyntaxError due to missing brackets

C. TypeError because data is not a list

D. IndexError because data[2] does not exist

Solution

1. Step 1: Check list length

   data has two elements: indexes 0 and 1 only.

2. Step 2: Accessing invalid index

   data[2] tries to access a third element which does not exist, causing IndexError.

3. Final Answer:

   IndexError because data[2] does not exist -> Option D

4. Quick Check:

   Index out of range = IndexError [OK]

Hint: Check list length before accessing index [OK]

Common Mistakes:

• Assuming index 2 exists
• Confusing syntax error with runtime error
• Ignoring zero-based indexing

5. Given a nested list nums = [[1, 2, 3], [4, 5], [6]], which code correctly prints all elements in order?

hard

A. print(nums[0][0], nums[1][1], nums[2][0])

B. for i in range(len(nums)):
print(nums[i])

C. for sublist in nums:
for num in sublist:
print(num)

D. for num in nums:
print(num)

Solution

1. Step 1: Understand nested iteration

   To print all elements, loop over each inner list, then each element inside it.

2. Step 2: Analyze options

   for sublist in nums: for num in sublist: print(num) uses two loops: outer for sublist, inner for num, printing each number.

3. Final Answer:

   for sublist in nums: for num in sublist: print(num) -> Option C

4. Quick Check:

   Nested loops print all elements [OK]

Hint: Use nested loops to access nested list elements [OK]

Common Mistakes:

• Printing inner lists instead of elements
• Using single loop only
• Hardcoding indexes without loops