Iterator protocol in Python - Time & Space Complexity

Time Complexity: Iterator protocol

O(n)

Understanding Time Complexity

When using the iterator protocol in Python, it's important to know how the time to get each item grows as the collection gets bigger.

We want to understand how the number of steps changes when we loop through items using an iterator.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

while True:
    try:
        item = next(my_iter)
        print(item)
    except StopIteration:
        break

This code uses the iterator protocol to get each item from a list one by one until all items are printed.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling next() on the iterator to get the next item.
• How many times: Once for each item in the list, until all items are retrieved.

How Execution Grows With Input

Each call to next() takes about the same time, and we call it once per item.

Input Size (n)	Approx. Operations
10	10 calls to next()
100	100 calls to next()
1000	1000 calls to next()

Pattern observation: The number of steps grows directly with the number of items. More items mean more calls.

Final Time Complexity

Time Complexity: O(n)

This means the time to go through all items grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Calling next() takes longer as we go further in the list."

[OK] Correct: Each next() call just moves to the next item, so it takes about the same time every time.

Interview Connect

Understanding how iterators work and their time cost helps you explain how loops behave in Python, a skill useful in many coding situations.

Self-Check

"What if the iterator was over a linked list instead of a Python list? How would the time complexity change?"

Practice

1. What does the __iter__ method do in the iterator protocol?

easy

A. Returns the iterator object itself

B. Returns the next item in the sequence

C. Stops the iteration

D. Creates a list from the iterable

Solution

1. Step 1: Understand the role of __iter__

   The __iter__ method is called to get an iterator object from an iterable.

2. Step 2: Identify what __iter__ returns

   It returns the iterator object itself, which has the __next__ method to fetch items.

3. Final Answer:

   Returns the iterator object itself -> Option A

4. Quick Check:

   __iter__ returns iterator object [OK]

Hint: Remember: __iter__ returns the iterator itself [OK]

Common Mistakes:

• Confusing __iter__ with __next__
• Thinking __iter__ returns the next item
• Assuming __iter__ stops iteration

2. Which of the following is the correct way to define an iterator class in Python?

easy

A. class MyIter:
def __next__(self):
pass

B. class MyIter:
def next(self):
pass

C. class MyIter:
def __iter__(self):
return self
def __next__(self):
pass

D. class MyIter:
def iter(self):
return self

Solution

1. Step 1: Check required methods for iterator

   An iterator class must have __iter__ returning self and __next__ to get next item.

2. Step 2: Match methods with options

   class MyIter: def __iter__(self): return self def __next__(self): pass correctly defines both __iter__ and __next__ methods.

3. Final Answer:

   Defines both __iter__ and __next__ methods -> Option C

4. Quick Check:

   Iterator class needs __iter__ and __next__ [OK]

Hint: Iterator class must have __iter__ and __next__ methods [OK]

Common Mistakes:

• Using next() instead of __next__()
• Missing __iter__ method
• Defining iter() instead of __iter__()

3. What will be the output of this code?

class Count:
    def __init__(self, limit):
        self.limit = limit
        self.num = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.num < self.limit:
            self.num += 1
            return self.num
        else:
            raise StopIteration

for i in Count(3):
    print(i, end=' ')

medium

A. Error: StopIteration not handled

B. 0 1 2

C. 1 2 3 4

D. 1 2 3

Solution

1. Step 1: Understand the iterator behavior

   The Count class starts num at 0 and returns num+1 until it reaches limit 3.

2. Step 2: Trace the loop output

   Loop prints 1, 2, 3 then raises StopIteration to end loop.

3. Final Answer:

   1 2 3 -> Option D

4. Quick Check:

   Count(3) yields 1 to 3 [OK]

Hint: StopIteration ends loop; count from 1 to limit [OK]

Common Mistakes:

• Starting count from 0 instead of 1
• Expecting 4 as output
• Thinking StopIteration causes error

4. Identify the error in this iterator implementation:

class MyIter:
    def __init__(self):
        self.data = [1, 2, 3]
        self.index = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.index <= len(self.data):
            result = self.data[self.index]
            self.index += 1
            return result
        else:
            raise StopIteration

medium

A. The condition should be self.index < len(self.data)

B. Missing return self in __iter__

C. Should raise StopIteration before returning result

D. Index should start at 1, not 0

Solution

1. Step 1: Analyze the index condition

   Index goes from 0 to len(data)-1. Using <= allows index == len(data), causing IndexError.

2. Step 2: Correct the condition

   Change condition to self.index < len(self.data) to avoid out-of-range access.

3. Final Answer:

   The condition should be self.index < len(self.data) -> Option A

4. Quick Check:

   Index must be less than length to avoid error [OK]

Hint: Use < to avoid index out of range errors [OK]

Common Mistakes:

• Using <= instead of < in index check
• Forgetting to return self in __iter__
• Starting index at 1 instead of 0

5. You want to create a custom iterator that returns only even numbers from 0 up to a given limit (exclusive). Which implementation correctly follows the iterator protocol and filters evens?

class EvenIterator:
    def __init__(self, limit):
        self.limit = limit
        self.current = 0
    def __iter__(self):
        return self
    def __next__(self):
        while self.current < self.limit:
            val = self.current
            self.current += 1
            if val % 2 == 0:
                return val
        raise StopIteration

hard

A. Fails because __iter__ should return a new object each time

B. Correct implementation returning even numbers up to limit

C. Incorrect because it returns odd numbers instead

D. Raises StopIteration too early, missing some evens

Solution

1. Step 1: Check iterator protocol methods

   Class defines __iter__ returning self and __next__ with loop and StopIteration.

2. Step 2: Verify filtering logic

   Inside __next__, it loops until limit, returns only even values, skipping odds.

3. Final Answer:

   Correct implementation returning even numbers up to limit -> Option B

4. Quick Check:

   Iterator filters evens correctly [OK]

Hint: Use while loop inside __next__ to skip unwanted items [OK]

Common Mistakes:

• Returning odd numbers by mistake
• Not raising StopIteration when done
• Returning new iterator in __iter__ each time