Is first(where:) Method always O(n) or it can be O(1) with usage of Set or Dictionary?

Question

I like to know if I use Set instead of Array can my method of first(where:) became Complexity:O(1)?

Apple says that the first(where:) Method is O(n), is it in general so or it depends on how we use it?

for example look at these two ways of coding:

var numbers: [Int] = [Int]()
numbers = [3, 7, 4, -2, 9, -6, 10, 1]

if let searchResult = numbers.first(where: { value in value == -2 })
{
    print("The number \(searchResult) Exist!")
}
else
{
    print("The number does not Exist!")
}

and this:

var numbers: Set<Int> = Set<Int>()
numbers = [3, 7, 4, -2, 9, -6, 10, 1]

if let searchResult = numbers.first(where: { value in value == -2 })
{
    print("The number \(searchResult) Exist!")
}
else
{
    print("The number does not Exist!")
}

can we say that in second way Complexity is O(1)?

Answer 1

It's still O(n) even when you use a Set. .first(where:) is defined on a sequence, and it is necessary to check the items in the sequence one at a time to find the first one that makes the predicate true.

Your example is simply checking if the item exists in the Set, but since you are using .first(where:) and a predicate { value in value == -2} Swift will run that predicate for each element in the sequence in turn until it finds one that returns true. Swift doesn't know that you are really just checking to see if the item is in the set.

If you want O(1), then use .contains(-2) on the Set.