Recursive enumerations in Swift - Time & Space Complexity

Time Complexity: Recursive enumerations

O(n)

Understanding Time Complexity

When using recursive enumerations, it is important to understand how the number of steps grows as the data structure gets bigger.

We want to know how the time to process these recursive values changes with their size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

indirect enum List {
  case end
  case node(Int, List)
}

func length(_ list: List) -> Int {
  switch list {
  case .end:
    return 0
  case let .node(_, tail):
    return 1 + length(tail)
  }
}
    

This code defines a recursive list and a function to count how many elements it has.

Identify Repeating Operations

• Primary operation: Recursive calls to length for each node in the list.
• How many times: Once for every element until the end of the list is reached.

How Execution Grows With Input

Each element in the list causes one recursive call, so the work grows directly with the number of elements.

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

Pattern observation: The number of steps grows in a straight line with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to count elements grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Recursive enumerations always cause exponential time because of recursion."

[OK] Correct: Here, each recursive call processes one element only once, so the time grows linearly, not exponentially.

Interview Connect

Understanding how recursion works with data structures like recursive enums helps you explain and reason about code clearly in interviews.

Self-Check

"What if the list was a tree with two recursive branches instead of one? How would the time complexity change?"