Sequence protocol for custom iteration in Swift - Time & Space Complexity

Time Complexity: Sequence protocol for custom iteration

O(n)

Understanding Time Complexity

When we create a custom sequence in Swift, we want to know how long it takes to go through all its items.

We ask: How does the time to iterate change as the sequence gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct CountDown: Sequence {
  let start: Int
  func makeIterator() -> some IteratorProtocol {
    var current = start
    return AnyIterator {
      if current <= 0 { return nil }
      defer { current -= 1 }
      return current
    }
  }
}

This code creates a countdown sequence from a starting number down to 1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each call to the iterator's next() method returns one number.
• How many times: The iterator runs once for each number from start down to 1.

How Execution Grows With Input

Each step in the countdown takes about the same time, so total time grows as we add more numbers.

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

Pattern observation: The time grows directly with the number of items to iterate.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The iterator runs faster because it uses a simple countdown."

[OK] Correct: Even simple steps add up, so the total time still grows with the number of items.

Interview Connect

Understanding how iteration time grows helps you explain performance clearly when creating custom sequences.

Self-Check

"What if the iterator returned two numbers per step instead of one? How would the time complexity change?"