Above file contains implementation of sequential search and binary search. You w
ID: 3711445 • Letter: A
Question
Above file contains implementation of sequential search and binary search. You will use the program to compare the performance of these two search techniques. Run the code few times and see what is going on. The program determines the execution times for binary search and sequential search for different list sizes. Evaluate the algorithm. After starting the program give the values as in the following interactions. Enter start list size: 100000 Enter end list size: 200000 Enter list size increment: 10000 Enter number of iterations for sequential search: 100 Enter number of items for binary search: 10001) Why would you run binary search many more times than sequential search? 2) Do some more evaluations to investigate the following issues. a) how do the execution times for the two algorithms compare for "small" lists? b) what happens to the execution time of sequential search as the list size grows? c) what happens to the execution time of binary search as the list size grows? d) how do the execution times for the two algorithms compare for "large" lists? 3) show supporting results for the answers to the above questions. 4) which algorithm would you employ for "small"lists? Would your answer change if the number of queries varies? 5) which algorithm would you employ for "large" lists? Would your answer change if the number of queries varies? 6) why do the two algorithms exhibit their respective behaviors?
Explanation / Answer
The binary search should be run more times than sequential search because the binary search algorithm is efficient and takes less time to execute as compared to the sequential search.
The worst case time complexity of the binary search algorithm is computed to
T(n)= O(log n)
and
The worst case time complexity of the sequential search algorithm is computed to
T(n)= O(n)
That is the reason the binary search should be preferred.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)