Algorithms
November 14, 2023Question 10146 – Time-Complexity
November 14, 2023Question 10144 – Time-Complexity
The average number of key comparisons done on a successful sequential search in list of length n is
Correct Answer: D
Question 4 Explanation:
Total comparisons required
= No. of comparisons if element present in 1st position + No. of comparisons if element present in 2nd position + …………. + No. of comparisons if element present in nth position
= 1 + 2 + 3 + … + n
= n(n+1)/2
= No. of comparisons if element present in 1st position + No. of comparisons if element present in 2nd position + …………. + No. of comparisons if element present in nth position
= 1 + 2 + 3 + … + n
= n(n+1)/2
Since there are n elements in the list, so average no. of comparisons
= Total comparisons/Total no. of elements
= (n(n+1)/2)/n
= n+1/2
log n
n-1/2
n/2
n+1/2
Subscribe
Login
0 Comments