O(lg n) bounds are fairly common for maps. C++'s for instance (though it also has unordered_map). The practical difference between O(1) bound and O(lg n) bound

O(lg n) bounds are fairly common for maps. C++'s for instance (though it also has unordered_map). The practical difference between O(1) bound and O(lg n) bound typically comes down to the constants anyway, making the big-O pretty much a wash for practical purposes.