Searching Algorithms Questions and Answers

Q: Given a set of n sorted distinct integers, the average case time complexity to search a key using linear search is

The average is (n+1)/2 comparisons.Assume the key is equally likely to be at any of the n positions. Finding it at position i costs i comparisons, so the average is the mean of 1, 2, ..., n.\[ \begin{aligned} \text{average} &= \frac{1 + 2 + \cdots + n}{n} \\ &= \frac{n(n+1)}{2n} = \frac{n+1}{2} \end{aligned} \]n/2 is the rough approximation, and (n-1)/2 undercounts by one. n - 1 is close to the worst case, not the average. Sorting does not help a linear search, which still scans from the start.

Q: What is the time complexity of binary search ?

Binary search runs in \(O(\log n)\) time.Binary search works on a sorted array. It compares the target with the middle element and discards half the remaining elements at every step. After k steps only \(n/2^{k}\) elements remain, so at most about \(\log_{2} n\) comparisons are needed: a million elements take only about 20.\(O(n)\) is linear search, which may examine every element. \(O(n \log n)\) is the cost of efficient sorting such as merge sort, and \(O(n^{2})\) that of simple sorts like bubble sort.

11.

Given a set of n sorted distinct integers, the average case time complexity to search a key using linear search is

A.n/2
B.(n-1)/2
C.(n+1)/2
D.n-1

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The average is (n+1)/2 comparisons.

Assume the key is equally likely to be at any of the n positions. Finding it at position i costs i comparisons, so the average is the mean of 1, 2, ..., n.

\[ \begin{aligned} \text{average} &= \frac{1 + 2 + \cdots + n}{n} \\ &= \frac{n(n+1)}{2n} = \frac{n+1}{2} \end{aligned} \]

n/2 is the rough approximation, and (n-1)/2 undercounts by one. n - 1 is close to the worst case, not the average. Sorting does not help a linear search, which still scans from the start.

Discuss in Forum

12.

What is the time complexity of binary search ?

A.\(O(\log n)\)
B.\(O(n^{2})\)
C.\(O(n)\)
D.\(O(n \log n)\)

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: A

Binary search runs in \(O(\log n)\) time.

Binary search works on a sorted array. It compares the target with the middle element and discards half the remaining elements at every step. After k steps only \(n/2^{k}\) elements remain, so at most about \(\log_{2} n\) comparisons are needed: a million elements take only about 20.

\(O(n)\) is linear search, which may examine every element. \(O(n \log n)\) is the cost of efficient sorting such as merge sort, and \(O(n^{2})\) that of simple sorts like bubble sort.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Searching Algorithms Questions and Answers || Searching Algorithms MCQ Questions and Answers || Searching Algorithms GK Questions and Answers || Searching Algorithms GK MCQ Questions || Searching Algorithms Multiple Choice Questions and Answers || Searching Algorithms GK || GK on Searching Algorithms || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Searching Algorithms Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications