Adobe Interview Question
InternsCountry: 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 ).