Question

Trace the steps for the Interpolation search to find the key = 198 in the following data set:

• 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 192, 198, 230, 235, 237, 250 [Points: 6] Which search algorithm will you select for the following data set (data will grow in the same order) and why? Also what will be the time complexity for that algorithm? [Points: 1 + 2 + 2 = 5]

100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250

What is the optimal block size to be skipped in jump search for the data set mentioned in Q4.c? Also, what is the time complexity?

Answer 1

To perform Interpolation search for the key = 198, we calculate a position and between bounds, adjust low/high, and repeat steps until found or out of range. For the growing data set, Interpolation search is the best choice with the time complexity of O(log log n) on average. The optimal block size for Jump search is the square root of the list's size, resulting in O(\(\sqrt{n}\)) complexity.

Step-by-step explanation:

Interpolation Search

To find the key = 198 in the provided data set using Interpolation search, the following steps can be traced:

1. Initialize the variables: low = 0 and high = (n-1) where n is the number of elements in the array.
2. While the array is sorted from low index to high index and the key is within the bounds of the array, calculate the position 'pos' where the value might be using the formula: pos = low + [((high - low) / (arr[high] - arr[low])) * (key - arr[low])].
3. Check the value at 'pos': if it matches the key (198), the search is successful.
4. If the key is larger than arr[pos], set low to pos + 1.
5. If the key is smaller than arr[pos], set high to pos - 1.
6. Repeat steps 2 to 5 until the value is found or the range is invalid indicating that the key is not present in the array.

Given the ordered growth of the data set, Interpolation search is suitable. Its average-case time complexity is O(log log n), but in the worst case, it can degrade to O(n).