Set.exists and Map.exists have O(N) complexity rather than O(log(N))

[alpitol]

The table in
https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/fsharp-collection-types#table-of-functions
has O(log(N)) complexity for Map.exists and Set.exists, but as they have to match arbitrary predicate, it should be O(N)

---

Document Details

⚠ Do not edit this section. It is required for learn.microsoft.com ➟ GitHub issue linking.

• ID: a0694330-a4e4-5a07-2b6b-8259b57e319a
• Version Independent ID: 71e9da59-27a1-6194-3a69-09b9d3a383d4
• Content: Collection Types - F#
• Content Source: docs/fsharp/language-reference/fsharp-collection-types.md
• Product: dotnet-fsharp
• GitHub Login: @cartermp
• Microsoft Alias: dotnetcontent

[cartermp]

Could you give an example of this? The F# set and map implementations use an AVL tree under the covers, and checking for existence is O(log(N)) for that kind of data structure.

[alpitol]

Set.contains is understandably O(log(N)), but not Set.exists, which searches elements with arbitrary predicate T -> bool.

[alpitol]

Example:

let m = [1..15] |> List.map (fun i -> i, i) |> Map.ofList
let predicate key value =
    printfn $"{key}"
    false
    
let result = Map.exists predicate m

[tuckstarsli]

#35656

[KathleenDollard]

@vzarytovskii

[BillWagner]

@vzarytovskii Can you comment on this issue?

[vzarytovskii]

I think we should fix it @T-Gro

[T-Gro]

The docs table has to be fixed. Arbitrary predicate search will be O(N).