Iterator interface implementation in PHP - Time & Space Complexity

Time Complexity: Iterator interface implementation

O(n)

Understanding Time Complexity

When we use the Iterator interface in PHP, we want to know how the time to go through items changes as the number of items grows.

We ask: How does looping through all elements behave as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class MyIterator implements Iterator {
    private array $items;
    private int $position = 0;

    public function __construct(array $items) {
        $this->items = $items;
    }

    public function current() {
        return $this->items[$this->position];
    }

    public function key() {
        return $this->position;
    }

    public function next(): void {
        $this->position++;
    }

    public function rewind(): void {
        $this->position = 0;
    }

    public function valid(): bool {
        return isset($this->items[$this->position]);
    }
}

$iterator = new MyIterator([1, 2, 3, 4, 5]);
foreach ($iterator as $key => $value) {
    echo "$key: $value\n";
}
    

This code defines a class that lets us loop over an array using the Iterator interface methods.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The foreach loop calls the Iterator methods repeatedly to access each item.
• How many times: Once for each element in the array, so as many times as the number of items.

How Execution Grows With Input

As the number of items grows, the number of method calls grows directly with it.

Input Size (n)	Approx. Operations
10	About 10 calls to current(), next(), valid()
100	About 100 calls to current(), next(), valid()
1000	About 1000 calls to current(), next(), valid()

Pattern observation: The work grows evenly as the list grows; doubling the items doubles the work.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Using the Iterator interface makes looping slower and more complex than a simple array loop."

[OK] Correct: The Iterator methods are called once per item, just like a normal loop visits each element once, so the time grows the same way.

Interview Connect

Understanding how iterators work and their time cost helps you explain how your code handles data step-by-step, a useful skill in many coding situations.

Self-Check

"What if the iterator's current() method did extra work each time it was called? How would that affect the time complexity?"