Hi,
I have found answer for this on web as:
To analyze the binary search algorithm, we need to recall that each comparison eliminates about half of the remaining items from consideration. What is the maximum number of comparisons this algorithm will require to check the entire list? If we start with n items, then after first comparison , list is reduced to n/2 items, after second comparison to n/4 items, after 3rd to n/8 items, after 4th to n/16 items and after ith comparison the list would be reduced to n/(2 raised to the power i) items. The link http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html says that n/(raised to the power i) is 1. I cant understand this. Somebody please guide me.
Zulfi.
I have found answer for this on web as:
To analyze the binary search algorithm, we need to recall that each comparison eliminates about half of the remaining items from consideration. What is the maximum number of comparisons this algorithm will require to check the entire list? If we start with n items, then after first comparison , list is reduced to n/2 items, after second comparison to n/4 items, after 3rd to n/8 items, after 4th to n/16 items and after ith comparison the list would be reduced to n/(2 raised to the power i) items. The link http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html says that n/(raised to the power i) is 1. I cant understand this. Somebody please guide me.
Zulfi.
Last edited: