In CMPSC 24, you should have learned about big-Oh analysis, i e. asymptotic wors
ID: 3820128 • Letter: I
Question
In CMPSC 24, you should have learned about big-Oh analysis, i e. asymptotic worst-case run-time analysis. a. What is the big-o analysis of a find(key) operation on a sorted array of n keys, implemented using binary search? Circle your answer. Note that log, in the context of big-O typically means log based 2, but since all logs are related by a constant factor, i.e. for any value of b, there is a constant C such that log Tilde 2 Tilde (x) = C log Tilde b Tilde(x). Explain why this is the running time for binary search. A "formal proof" is not required mdash just a brief intuitive explanation that shows you understand why this is the running time.Explanation / Answer
In binary search instead of starting the search linearly from the ist elemwnt of the array, it begins from the middle of the list of items. If the key are looking for is that middle item ,our task is over. If it is not the desired one, we can use the ordered list to eliminate half of the remaning items by limiting our search to only half the list. If the key we are looking has a value greater than the middle item we restrict our search to right half of the list otherwise we search left half. We then continue our search with one half either right or left i.e, process is repeated: begin with middle item, compare and then decide. We go on splitting the list this way and eliminate the large part of search space.
comparison number of items left
1st n/2
2nd n/4
3rd n/8
....
k n/2k
Therfore, the total number of comparisons to reach this point is k where n/2k= 1
applying log on bothsides
log(n/2k) = log 1
log n - k log 2 = 0
log n= k or k=log n
.ie., the maximum number of comparisons required are logarithmic to the number of elements in an array. hence time complexity is O(log n)