3 ms·
Honest asymptotic complexity for search trees and tries
- zogrodea 3y agoThe key comparison cost is real. I remember coding a balanced binary tree of integers once in OCaml and wondering why the standard library's implementation was 2x faster. The reason was that the tree I had coded used polymorphic compare (the >, < and = operators) which isn't specialised for a particular type while the standard library's balanced tree would use a specialised `Int.compare` function. Of course other types have varying comparison costs too.