Archives

Oh! Oops, didn’t catch that. …

Comment on “BList” by Daniel Stutzbach

Oh! Oops, didn't catch that. Yes, insort and family are currently O((log n)**2) Do you see a clever way to make it O(log n) by using the structure?

Even if it keeps track of where it is in the tree (rather than going back to the root every time), I think it still works out to O((log n)**2), albeit with a smaller constant factor.

There's no value information inside the tree, so it has to go all the way down to a leaf to make each comparison.

Share

Comments are closed.