alleryStart learning →Linear search over n elements for key x has best-case and worst-case running times of
Abest = O(n) all cases, worst = O(n²) total
Bbest = O(log n) for sorted, worst = O(n)
Cbest = O(n) always, worst = O(n) always
Dbest O(1) if x at index 0, worst O(n) otherwise
Answer & Solution
Correct answer: D. best O(1) if x at index 0, worst O(n) otherwise
Linear search starts comparing from index 0. If x sits at index 0 we are done in one comparison (constant, O(1)).
If x is at index n-1 or not in the array, we make n comparisons (linear, O(n)).
The lecture works through exactly this example.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.