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