what is the time complexity of removing first element in set??
Set functionality
hello @shampblocks
set is implemented using self balancing binary tree (i guess red black tree).
and in any self balancing tree deletion will never exceed O(log(n)) where n is number of element in ur set.
so it will be O(log(N) ) on average we treat it as O(1)
Why we treat it as O(1)??
it is amortised time complexity.
Internally elements of a set are stored in a balanced binary tree. Balanced tree is a tree where maximal height difference between any left and right subtree of any node is 1.
Maintaining balanced structure is important to guarantee that a search of any element in the tree (in the set) takes in worst case O(log(n)) steps.
Removal of an element may destroy balance. To restore balance rotations must be performed. In some cases a single removal causes several rotations so that the operation takes O(log(n)) steps, but in average a removal takes O(1) steps.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.