Algorithms
November 14, 2023Question 10146 – Time-Complexity
November 14, 2023Algorithms
| Question 22 |
The average number of key comparisons done on a successful sequential search in list of length n is
| log n | |
| n-1/2 | |
| n/2 | |
| n+1/2 |
Question 22 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
Correct Answer: D
Question 22 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
Subscribe
Login
0 Comments