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.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for