Search Algorithms

Question 1

Time complexity of linear search

Answer 1

O(n)

Question 2

Time complexity of binary search

Answer 2

O(log n)

Question 3

Time complexity of hash table search

Answer 3

Without collision resolution: O(1)
With collision resolution: O(n)

Question 4

For a hash table, a hash function should:

Answer 4

1. Take an input key of any length
2. Return a location of fixed length
3. Location should be unique to the key

Returns an output hash index of fixed size

Question 5

For a hash table, a key should be:

Answer 5

Immutable (so that its hashed location is always the same)

Question 6

Features of an ideal hash function

Answer 6

• Use all input data
• Small difference in input results in large difference in hash value
• Output should be uniformly distributed across all possible hash values

Question 7

The key steps for Binary Search are:

Answer 7

1. Handle the base case (empty/single-element array)
2. Initialise start = 0 and end = array.length - 1
3. Determine middle index mid
4. Check item at mid:
   
   • if match, return mid
   • if search key less than mid item, update end to mid - 1
   • if search key greater than mid item, update start to mid + 1
5. If start > end (no match found), return none or display/raise error, else repeat from step 3

Question 8

collision resolution

Answer 8

open addressing (generation of new location):
1. hash key to location
2. if key matches store key and value pair at location
3. else, rehash key to new location and repeat step 2
4. if no more location available return error
close addressing (each location in the table is a linked list):
1. hash key to location
2. check if linked list at location have the key (yes, end/ update)
3. else, add key-pair value to end of linked list