I want to analyse the time complexity for Unsuccesful search using probabilistic method in a Hash table where collisions are resolved by chaining through a doubly linked list. And the doubly linked list is kept in sorted order (Ascending).
I proceeded in the following way: We will stop if the element in the linked list is greater than the element to be searched, otherwise continue the search. I can understand that this will be better than the normal Unsuccesful search in Hashing i.e. $O(\alpha + 1)$. But how do I do exact analysis of average case time complexity in this case using Expectations in Probability.
Edit: The Keys are randomly distributed from 1 to n and the number of slots in Hash table are m.