search

crossbeam-rs / crossbeam

Tools for concurrent programming in Rust
Apache License 2.0
7.49k stars 470 forks source link

Complexity O() #1099

Closed saefstroem closed 7 months ago

saefstroem commented 8 months ago

What is the complexity of read write operations in SkipMap and SkipSet? These are rather important metrics that should be part of the README.md imo.

caelunshun commented 7 months ago

O(log n) average, O(n) worst case for lookups, insertions, and deletions. I don't think the O(n) worst case is likely to occur typically.

saefstroem commented 7 months ago

O(log n) average, O(n) worst case for lookups, insertions, and deletions. I don't think the O(n) worst case is likely to occur typically.

Excellent, thanks for this.