Worst-Case Analysis of Linear Search

Verified Sources

Sep 11, 2026

The correct answer is (iv) the item is the last element in the array or is not there at all.

Linear search examines elements from the beginning of an array, one at a time. It stops when either:

The target item is found.
Every element has been checked and the target is absent.

For an array containing $n$ elements, the greatest number of comparisons occurs when the target is at the final position or when it does not appear in the array. In both cases, the algorithm examines all $n$ elements, giving a worst-case running time of $O(n)$ .2

Linear search - Defines linear search and gives its best, average, and worst comparison counts. ↩
Linear Search Algorithm - Describes sequential checking, $O(1)$ best case, and $O(n)$ worst case. ↩

Linear Search: Best, Average, and Worst Cases

Why the Last Element and “Not Found” Are Equivalent

Consider the array:

Index	0	1	2	3	4
Value	12	7	25	4	19

Suppose the algorithm searches from left to right.

Searching for $12$ requires $1$ comparison.
Searching for $25$ requires $3$ comparisons.
Searching for $19$ requires $5$ comparisons.
Searching for $30$ , which is absent, requires $5$ comparisons.

Thus, both “target at the last index” and “target absent” require the maximum possible number of comparisons: $n$ .2

Worst-case analysis focuses on the input that causes the greatest number of operations, not merely on whether the search succeeds.

Linear search - Defines linear search and gives its best, average, and worst comparison counts. ↩
What Is Linear Search? - Explains why a final-position or absent target requires scanning the entire collection. ↩

Determine the Worst Case

1
Step 1
Standard linear search begins at the first array element and moves toward the last.
2
Step 2
The algorithm performs one comparison for each inspected element.
3
Step 3
If the target is the last element, all $n$ elements must be inspected before the match is discovered.
4
Step 4
If the target is absent, the algorithm must inspect all $n$ elements before it can conclude that no match exists.
5
Step 5
Both situations require $n$ comparisons, so they jointly describe the worst case.
6
Step 6
The correct option is (iv): the item is the last element in the array or is not there at all.

Complexity Comparison

Let $n$ be the number of elements in the array.

Case	Target position or condition	Comparisons	Complexity
Best case	First element	$1$	$O(1)$
Average case	Typically somewhere in the interior	Approximately $(n+1)/2$ for equally likely successful searches	$O(n)$
Worst case	Last element	$n$	$O(n)$
Worst case	Target absent	$n$	$O(n)$

The average number of comparisons for a successful search, assuming each position is equally likely, is:

\frac{1+2+\cdots+n}{n} = \frac{n+1}{2}

Even though the average and worst cases are both classified as $O(n)$ , the worst case is specifically determined by the maximum number of comparisons.2

Big-O notation ignores constant factors and lower-order terms. Therefore, both $n$ and $(n+1)/2$ are classified as $O(n)$ .

Linear search - Defines linear search and gives its best, average, and worst comparison counts. ↩
Linear Search in C - Discusses average-case performance and comparison behavior. ↩

linearSearch(array, target):
    for i from 0 to length(array) - 1:
        if array[i] == target:
            return i
    return -1

Trace a Worst-Case Search

1
Step 1
Use the array $[8, 3, 11, 6, 14]$ and search for $14$ .
2
Step 2
Compare $8$ with $14$ . They differ, so continue.
3
Step 3
Compare $3$ with $14$ . They differ, so continue.
4
Step 4
Compare $11$ with $14$ . They differ, so continue.
5
Step 5
Compare $6$ with $14$ . They differ, so continue.
6
Step 6
Compare $14$ with $14$ . The target is found after $5$ comparisons.
7
Step 7
Because the array contains $n=5$ elements, the search used $n$ comparisons. This is a worst-case successful search.

Number of Comparisons in a Five-Element Array

The last-element and absent-target cases both require the maximum number of comparisons.

Exam Strategy

When a question asks for the worst case of linear search, look for the situations that force the algorithm to inspect every element: the target is last or the target is absent.

Do Not Choose Only the Last Element

Option (iii) is incomplete. An unsuccessful search also examines every element, so the complete answer is option (iv).

Common Questions and Clarifications

Linear Search Worst-Case Review

1 / 5

Question · Term

What is the correct answer?

Click to reveal

Answer · Definition

Option (iv): the item is the last element in the array or is not there at all.

Final Answer

(iv) The item is the last element in the array or is not there at all.

Both cases force linear search to inspect every element. For $n$ elements, the algorithm performs $n$ comparisons, so the worst-case time complexity is $O(n)$ .2

Linear search - Defines linear search and gives its best, average, and worst comparison counts. ↩
Linear Search Algorithm - Describes sequential checking, $O(1)$ best case, and $O(n)$ worst case. ↩

Knowledge Check

Question 1 of 4

Q1Single choice

In which situation does linear search perform the maximum number of comparisons?

The target is the first element

The target is in the middle of the array

The target is the last element or is absent

The array contains duplicate values

Explore Related Topics

Merge Sort: Working, Example, and Complexity Analysis

Shortest-Path Algorithms for a City Road Network

A city road network is modeled as a graph, and the appropriate single‑source shortest‑path algorithm depends on the edge‑weight properties.

All edges equal → use BFS, which finds minimum‑edge paths in $O(|V|+|E|)$ time.
Non‑negative varying weights → use Dijkstra’s algorithm, greedy with a min‑priority queue, running in $O((|V|+|E|)\log|V|)$ .
Some negative weights → use Bellman–Ford, relaxing all edges $|V|-1$ times ( $O(|V||E|)$ ) and detecting negative cycles.
The selection rule:
$\text{Algorithm}=\begin{cases}\text{BFS} & \text{if all }w(e)\text{ equal}\\ \text{Dijkstra} & \text{if }w(e)\ge0\\ \text{Bellman-Ford} & \text{if any }w(e)<0\end{cases}$
A reachable negative cycle means no finite shortest path exists.

Belady's Anomaly and Why LRU and Optimal Page Replacement Avoid It

Browse all research articles

Worst-Case Analysis of Linear Search

Footnotes

Linear Search: Best, Average, and Worst Cases

Why the Last Element and “Not Found” Are Equivalent

Footnotes

Determine the Worst Case

Complexity Comparison

Footnotes

Trace a Worst-Case Search

Number of Comparisons in a Five-Element Array

Exam Strategy

Do Not Choose Only the Last Element

Common Questions and Clarifications

Linear Search Worst-Case Review

What is the correct answer?

Final Answer

Footnotes

Knowledge Check

Explore Related Topics