Hey guys, I just designed a new container algorithm (think stl::set) and I wanted to know if you all think it looks useful.

AVL tree (for comparison):

Inserting in sorted order: O(logn)

Removing with sorted order: O(logn)

Finding: O(logn)

Iterating in sorted order: O(n)

My algorithm:

Inserting in sorted order: O(sqrt(n)), but with average time of logn

Removing with sorted order: O(1)

Finding: O(1)

Iterating in sorted order: O(n)

I think it's really cool, but the O(sqrt(n)) insertion worries me. It would only happen if it was fed something that was already sorted, which I think would be a common case.

- Evan Ovadia