You have just been hired to develop a program that searches in a huge file having 10 million elements. This file stores the social insurance numbers of the customers of an investment company. You have discussed multiple strategies in order to obtain the best average search time. The best option is to sort the elements so that binary search can be used for an average search time of O(log2 n), which would result in a maximum of 24 look-ups. Using sequential search would result in an average search time of 5,000,000 look-ups, 1 look-up for the best case and 10 million look-ups for the worst case. However, keeping the elements sorted would be very time-consuming as new elements are added or removed frequently (that by itself would cost a complexity of n as shifting may be needed!). Consequently, the team leader decided to just go with a sequential search. You accepted his decision but proposed him to use multiple-threads to speed-up the processing.

The computing system has a single CPU, and is using a Round-Robin scheduling algorithm with a time quantum of 20 ms (milliseconds and has a context switch time of 1 ms. Also, each search operation (that is, each array loop, or each single iteration over the array) requires 5 ns (nanoseconds). The search application has other operations beside the loop but their execution time is not significant and is not taken into consideration. For each of the questions below, your answer should not exceed 1/2 a page (each)

1. Explain whether using multiple threads would really provide an advantage over using just a single thread. You need to explain and justify your answer for the most optimal solution (best case), as well as for worst case and the average case.

2. Whether or not the use of multi-threading is more advantageous than single-threading, discuss another type of application (give a completely distinct real-life problem that is different from the search problem described in this question) that could benefit more by using multi-threading in a single CPU environment.

3. Consider a load of 2 threads handling the search operation such that each thread searches one half of the array. Assume that both threads are on the ready queue at time t=0 and that the search value is not found in the list of elements. a. Draw the Gantt chart. b. Calculate the average turnaround time and provide the turnaround time for each thread.

4. Suppose we use a load of 4 threads instead of 2, and that all of them are on the ready queue at time t=0. Would there be any change in the average turnaround time as little as it can be? Explain - show all your numbers/calculations.

5. Now assume 4 CPUs and a load of 4 threads, and that all threads are on the ready queue at time 10. Will that improve the performance of the search algorithm as opposed to using a single CPU? Explain clearly why or why not?