Iterating over lists in Python - Time & Space Complexity

Time Complexity: Iterating over lists

O(n)

Understanding Time Complexity

When we go through each item in a list one by one, it takes some time. We want to understand how this time changes when the list gets bigger.

The question is: How does the time to look at every item grow as the list grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def print_items(items):
    for item in items:
        print(item)

my_list = [1, 2, 3, 4, 5]
print_items(my_list)

This code goes through each item in a list and prints it out.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each item in the list.
• How many times: Once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the number of times we print grows the same way.

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

Pattern observation: The number of steps grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means if the list doubles in size, the time to go through it also doubles.

Common Mistake

[X] Wrong: "Looping through a list always takes the same time no matter how big the list is."

[OK] Correct: The time depends on how many items are in the list. More items mean more steps.

Interview Connect

Understanding how looping through lists grows with size helps you explain your code clearly and shows you know how programs handle data efficiently.

Self-Check

"What if we nested one loop inside another to go through the list twice? How would the time complexity change?"

Practice

1. What does the following code do?

for item in [1, 2, 3]:
    print(item)

easy

A. Prints the whole list once

B. Prints numbers 1 to 3 without spaces

C. Prints each number 1, 2, and 3 on a new line

D. Causes an error because of the loop

Solution

1. Step 1: Understand the for loop over a list

   The loop goes through each element in the list [1, 2, 3] one by one.

2. Step 2: Print each element during iteration

   Each element (1, then 2, then 3) is printed on its own line because of the print statement.

3. Final Answer:

   Prints each number 1, 2, and 3 on a new line -> Option C

4. Quick Check:

   Loop prints items one by one [OK]

Hint: For loops print each list item separately [OK]

Common Mistakes:

• Thinking it prints the whole list at once
• Expecting numbers to print on the same line
• Confusing loop variable with list itself

2. Which of these is the correct syntax to loop over a list named fruits?

easy

A. for fruit in fruits:
print(fruit)

B. for fruits in fruit:
print(fruits)

C. loop fruit in fruits:
print(fruit)

D. for fruit to fruits:
print(fruit)

Solution

1. Step 1: Identify correct for loop syntax

   The correct Python syntax uses 'for variable in list:' to loop over items.

2. Step 2: Check each option

   for fruit in fruits: print(fruit) uses 'for fruit in fruits:', which is correct. Others use invalid keywords or reversed names.

3. Final Answer:

   for fruit in fruits: print(fruit) -> Option A

4. Quick Check:

   Use 'for item in list:' syntax [OK]

Hint: Remember: for variable in list: [OK]

Common Mistakes:

• Swapping variable and list names
• Using wrong keywords like 'loop' or 'to'
• Missing colon after for statement

3. What is the output of this code?

numbers = [2, 4, 6]
sum = 0
for n in numbers:
    sum += n
print(sum)

medium

A. 12

B. 0

C. 246

D. Error

Solution

1. Step 1: Understand the loop adding numbers

   The loop adds each number in the list [2, 4, 6] to sum, starting from 0.

2. Step 2: Calculate the total sum

   sum = 0 + 2 + 4 + 6 = 12

3. Final Answer:

   12 -> Option A

4. Quick Check:

   Sum of list items = 12 [OK]

Hint: Add each item inside the loop to get total [OK]

Common Mistakes:

• Printing sum before loop
• Concatenating numbers as strings
• Forgetting to initialize sum to 0

4. Find the error in this code:

items = [10, 20, 30]
for i in items
    print(i)

medium

A. List name is incorrect

B. Wrong variable name in loop

C. Indentation error in print

D. Missing colon after for statement

Solution

1. Step 1: Check for syntax errors in for loop

   The for loop must end with a colon ':' to be valid syntax.

2. Step 2: Identify missing colon

   The code misses ':' after 'for i in items', causing a syntax error.

3. Final Answer:

   Missing colon after for statement -> Option D

4. Quick Check:

   For loops need ':' at end [OK]

Hint: Always put ':' after for loop header [OK]

Common Mistakes:

• Forgetting colon after for statement
• Using wrong variable names
• Incorrect indentation of print

5. You have a list of lists: data = [[1, 2], [3, 4], [5, 6]]. How do you print all numbers one by one using iteration?

hard

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

B. for sublist in data:
for num in sublist:
print(num)

C. for i in range(len(data)):
print(data[i])

D. for num in data:
print(num)

Solution

1. Step 1: Understand nested lists and iteration

   Each item in data is a list itself, so we need two loops: one for each sublist, one for numbers inside.

2. Step 2: Use nested for loops to access all numbers

   The outer loop goes through each sublist, the inner loop prints each number inside that sublist.

3. Final Answer:

   for sublist in data: for num in sublist: print(num) -> Option B

4. Quick Check:

   Nested loops print all inner items [OK]

Hint: Use nested loops for lists inside lists [OK]

Common Mistakes:

• Trying to print sublists directly
• Using single loop only
• Accessing wrong indexes causing errors