What is the worst case time for a serial search in an array? What about binary s
ID: 3768527 • Letter: W
Question
What is the worst case time for a serial search in an array? What about binary search? What about your average hash table? (Express answers as O (n) or type [logarithmic, constant etc.] When using an array to do a binary search, what additional requirement is placed on the array? What is the definition of a collision in a hash table? What kind of initialization needs to be done for an open-address hash table? What about a chained hash table? A chained hash table has an array size of 512; what is the maximum number of entries that can be placed in the table? Given a hash table with array size s holding m items - what is the correct formula for the load factor?Explanation / Answer
Answer:
1) Worst-Case time for serial search:
For an array of n elements, the worst-case time for serial search is O(n).
Worst-Case time for binary search:
The worst-case time for binary search is proportional to log2 N.So,the number of times N can be divided in half before there is nothing left,using big-O notation, is O(log N).
Average Case Time Complexity Hash tables :
It's not only the size but also the hash collisions which determine time complexity for hashing. It won't happen in O(1) time, but the average case is still close to O(1).
Worst-case complexity of Hash tables is O(n).
3.
When searching an array, the binary search process utilizes this same concept of splitting intervals in half as a means of finding the "key" value as quickly as possible.Array must be "sorted".
4.
Two keys mapping to the same location in the hash table is called “Collision”
Collisions can be reduced with a selection of a good hash function but it is not possible to avoid collisions altogether,unless we can find a perfect hash function.
5.
Initialization required for an open-address hash table : The key at each array location must be initialized.
Initialization required for chained hash table : The head pointer of each chain must be set of NULL.
It's not only the size but also the hash collisions which determine time complexity for hashing. It won't happen in O(1) time, but the average case is still close to O(1).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.