he said that for rehashing, we might need to traverse the array, so complexity will become O(n), so how does it become O(1), I am not able to understand this
I did not understand the last thing he said
Hi @apoorvsingh27,
See he said when we rehash we may traverse the whole array and hence the complexity will become O(n) for rehashing but the thing is that rehashing does not occur everytime a element is added. It occurs when our total elements/sizeofarray becomes greater than a lambda constant . So for size of let us say 32 and lambda around 0.75 we can perform 24 operations in O(1) and then one operation of O(n) takes place to rehash so overall as he said in average case we have time complexity of O(1) as rehashing does not occur everytime a element is added .Hope this helps
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.