Run the code few times and see what is going on. The program determines the exec
ID: 3711624 • Letter: R
Question
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 iterations for binary search: 1000 1) Do some 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? 2) show the supporting results for your answers to the above questions. 3) which algorithm would you employ for "small" lists? Would your answer change if the number of queries varies? 4) which algorithm would you employ for "large" lists? Would your answer change if the number of queries varies? 5) why do the two algorithms exhibit their respective behaviors?Explanation / Answer
Solution:
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. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.