PGEE Sample Question

Question

Consider the following four data structures: array, binary search tree, hash table, and a linked list. Which of the following options arranges them in non-decreasing order of worst case runtime for searching?

• A. Array, Binary Search Tree, Linked List, Hash Table
• B. Hash Table, Binary Search Tree, Linked List, Array
• C. Binary Search Tree, Hash Table, Array, Linked List
• D. Hash Table, Linked List, Binary Search Tree, Array

I think it will be $O(n)$ for all four of them in the worst cases: Array-unsorted, BST-skewed, Hash Table-mapped to one location only, $LL$ has $O(n)$.

Comments

Why will it  be  O(n) in the worst  case for a hash table  ?  Shouldn't it be O(1)  ?

---

In chaining/open hashing, more than one item at one location are arranged using a LL. Thus, in worst case all n items can get mapped to a single location forming a LL of size n.

---

thanks  , I forgot  the low level implementations  after I started using python

Answer 1

B