In Java What is the worst case time for a serial search in a

In Java

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?

Solution

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 period N can be divided in half prior to 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).

2)
When searching an array, the binary search process utilizes this same concept of splitting intervals in half as denotes of result the \"key\" value as fast as possible. Array must be \"sorted\".

3)
Two keys mapping to the similar location in the hash table is named as Collision
Collisions can be decreased with a choice of a good hash function but it is not probable to evade collisions altogether, if not we can locate a perfect hash function.