Swift's map and filter functions time complexity

Question

I have implemented the numJewelsInStones function below in two different ways using Swift 4.

I would like to compare the time and space complexity of each implementation. However, I am using some native method's such as filtering a string in one implementation and then mapping a string to an array of single characters in the other implementation. I would like to know the time complexity of these native functions. Also, what if I used string range to get the occurrences of each character in the string. I would like to understand how these native functions, in Swift specifically, affect the overall Big O.

Implementation 1: filtering a string (with the for loop if I ignore the filter function I would say the Big O is O(n), is this correct?)

//J - represents types of stones that are jewels
//S - represents the stones I have
func numJewelsInStones(_ J: String, _ S: String) -> Int { 
    var sum = 0 //Sum - represents how many of the stones I have are also jewels
    for jewel in J {
        sum = sum + S.filter {$0 == jewel}.count //add sum of occurrences for each stone that is a jewel
    }
    return sum 
}
print(numJewelsInStones("aA", "aAAbbbb")) //prints 3
print(numJewelsInStones("z", "ZZ"))       //prints 0

Implementation 2: the first thing I do is mapping the string to an array of single characters or else I would get the error 'cannot substring a value of type [ String: Int] with an index of type character' on the line counts[stone] = (counts[stone] ?? 0) + 1

UPDATE: just noting that I realized that I don't even need to map the string to an array of characters if I just change the definition of the counts dictionary to var counts: [Character: Int] = [:] that would avoid the error above. Oops. I am leaving it as is for the sake of the question though.

func numJewelsInStones2(_ J: String, _ S: String) -> Int {
        let jewels = J.map { String($0) }
        let stones = S.map { String($0) }
        var counts: [String: Int] = [:]
        var sum = 0
    for stone in stones {
        counts[stone] = (counts[stone] ?? 0) + 1 //frequency count dict
    }
    for jewel in jewels { //for every jewel
        if let count = counts[jewel]  { //if the jewel exists in the frequency count dict
            sum = sum + count //add its count to the total sum
        }
    }
    return sum
}

print(numJewelsInStones2("aA", "aAAbbbb")) //prints 3
print(numJewelsInStones2("z", "ZZ"))       //prints 0

Answer 1

All higher-order functions in the Swift standard library, such as map, flatMap/compactMap, filter and reduce have O(n) time complexity in general, since all of them work on the full collection they're called on and they visit each element exactly once, so they have linear time complexity.

Taking this into consideration, your first implementation has O(J*S) time complexity, since for every element in J you iterate through all elements of S using filter.

Your second implementation on the other hand has roughly linear time complexity depending on which String has more Characters in it, S or J, its time complexity is O(J) or O(S), since you don't have any nested loops, you only iterate through J and S sequentially.

Whether Implementation 1 or 2 is more efficient depends on the size of J and S completely.

Answer 2

flatMap / compactMap take O(m + n), where n is the length of this sequence and m is the length of the result.

This is written in iOS SDK documentation.