why In a hash table in which collisions are resolved by chaining an unsuccessful search and successful search both have same time complexity o(1+@). where @ is a load factor.
reply soon
Unsuccessful search
O(1) to reach array location, O(@) to traverse the list or to reach the end of the list. (Please note We must reach the end of the list then only we can say that the element was not in the table),
so T(n) = 1+@ where @ = n/m, number of elements/ number of array locations.
Successful search
Assume that new element is inserted at the end of the linked list. Upon insertion of the ith element, the expected length of list is (i-1)/m.
In case of successful search, the expected no. of elements examined is 1 more.
So the time need T(n) = 1/n(∑1<=i<=n(1 + (i-1)/m)
= 1 + n/2m -1/2m
= 1 + @/2 -1/2m = O(1+@)
Comment if you don’t get any point of my answer 
1 Like