## Adobe Interview Question

Interns**Country:**India

>> **Find/insert/remove in ordered set (actually balanced BST) is O( log n ).

Can you explain this step a bit further.

Thanks

In C++ set/multiset is implemented using a height balanced binary search tree (AVL or red-black tree). As a result these operations are bounded by the tree height, which is O( log n ).

By maintaining an ordered set of segments we can add new segments in O( log n ) time** and report max in O(1) time (here n means at most n segments have been processed so far).

- lasthope November 25, 2013**Find/insert/remove in ordered set (actually balanced BST) is O( log n ). Since the total number of merged segments cannot be more than n, merging operation should be amortized O( log n ).