-
Book Overview & Buying
-
Table Of Contents
Hands-On Data Structures and Algorithms with Python – Third Edition - Third Edition
By :
On average, how many comparisons are required in a linear search of n elements?
The average number of comparisons in linear search will be as follows. When a search element is found at the 1st position, 2nd position, 3rd position, and similarly at the nth position, correspondingly, it will require 1, 2, 3… n number of comparisons.
Total average number of comparisons

= 
= 
Assume there are eight elements in a sorted array. What is the average number of comparisons that will be required if all the searches are successful and if the binary search algorithm is used?
Average number of comparisons = (1+2+2+3+3+3+3+4)/8
= 21/8
= 2.625

Figure A.12: Demonstration of number of the comparisons in the given array
What is the worst-case time complexity of the binary search algorithm?
O(logn).
The worst-case scenario of the...