Time complexity of Swift 'compactMap' Sequence's method

user_6324055 0
Viewed 200

Swift documentation states that compactMap() method for sequenced has a time complexity of O(n + m) where n is the length of the sequence and m is the length of the result.

However, when looking at the implementation in the standard library I cannot understand why:

public func _compactMap<ElementOfResult>(
    _ transform: (Element) throws -> ElementOfResult?
  ) rethrows -> [ElementOfResult] {
    var result: [ElementOfResult] = []
    for element in self {
      if let newElement = try transform(element) {
        result.append(newElement)
      }
    }
    return result
  }

There is only one loop over the sequence elements, it should be O(n).

sequence swift
1 Answers

The documentation doesn't actually state whether that's the time or memory complexity of the algorithm.

The time complexity is O(n) indeed, however, the memory complexity is O(n+m), since the original Sequence of size n is kept in memory, while a new Array of size m is also created.

user_46678350
Related