Is IndexList.IndexOf complexity correct?

fsprojects / FSharp.Data.Adaptive

On-demand adaptive/incremental data for F# https://fsprojects.github.io/FSharp.Data.Adaptive/

MIT License

250 stars 24 forks source link

Is IndexList.IndexOf complexity correct? #61

Closed Thecentury closed 4 years ago

Thecentury commented 4 years ago

IndexList has IndexOf by Index operation:

/// Tries to find the position for the given Index or -1 if the Index does not exist. O(N)
member x.IndexOf(index : Index) =
    MapExt.tryIndexOf index content |> Option.defaultValue -1

Is its complexity really O(N)? I looked into the implementation and it seems to be a search in a binary tree, therefore having the O(log(N)) complexity, isn't it?

krauthaufen commented 4 years ago

Correct, thanks for the report, I will fix that soon... Btw. many of the hashmap/hashset complexities are actually O(min(32,log N)) but I annotated them with log N...

krauthaufen commented 4 years ago

done, thanks again!