0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is anything known about the distribution of data? If not, then I don't think you can do anything better than concluding O(loadFactor+1) $\endgroup$
    – Rinkesh P
    Sep 21, 2022 at 9:23
  • $\begingroup$ @RinkeshP, The keys are distributed randomly between 1 and n. $\endgroup$
    – Equation_Charmer
    Sep 21, 2022 at 9:44
  • $\begingroup$ Even with this information, you gain no insight, as the element you are searching might be greater than the last element(greatest) of its chain. Until you know how your data within a chain is distributed(other than being a uniform random distribution) I doubt this can be taken any further. $\endgroup$
    – Rinkesh P
    Sep 21, 2022 at 9:58
  • $\begingroup$ Yes that is the worst case, however I need a bound for average time analysis. $\endgroup$
    – Equation_Charmer
    Sep 21, 2022 at 10:00

1 Answer 1

Reset to default
0
$\begingroup$

Let $\alpha = \frac{n}{m}\ $ where $n$ = total no. of elements in hashtable ,$m$ = number of slots in hashtable, be the load factor or Average number of elements in a chain.

Given that each chain is sorted, an unsuccessful attempt at search would require $1$ comparison in the best case and $\alpha$ comparisons in the worst case. The expected no. of comparisons for the same is

$\frac{1}{\alpha }(1+2+3+....+\alpha) = \frac{\alpha (\alpha +1)}{2\alpha } = \frac{\alpha +1}{2}$

yielding an average case complexity of $O(\frac{\alpha +1}{2}+1)$.

P.S. If your chains are sorted then you can lower the complexity to $O(\log_{2}\alpha+1)$ by using binary search(depending on your implementation of linked list)

Improve this answer
$\endgroup$
6
  • $\begingroup$ You can't perform a binary search in a linked list. (And the length is not $n$.) $\endgroup$
    – user16034
    Sep 21, 2022 at 10:49
  • $\begingroup$ Implementation details, if its implemented as a typical "linked list" then no. if its simply an array then yes. $\endgroup$
    – Rinkesh P
    Sep 21, 2022 at 10:50
  • $\begingroup$ The question explicitly says linked list. But how would you organize the collision lists in an array ? $\endgroup$
    – user16034
    Sep 21, 2022 at 10:53
  • $\begingroup$ Linked list as an abstraction. I simply provided a possibility where the implementation could be an array implementation(the hashtable is a 2d array). Similarly collisions could be handled by using binary search tress as well. $\endgroup$
    – Rinkesh P
    Sep 21, 2022 at 10:57
  • $\begingroup$ Yves, you can implement a linked list as one or more arrays, which may give you actually better performance for large linked lists. However, the linked lists for overflow of a hash table are supposed to be small. If they are not small, you'd increase the number of slots in the hash table which will give you much better results. $\endgroup$
    – gnasher729
    Sep 21, 2022 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.