15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Best, average and worst case analysis measures an algorithm's cost on different inputs of the same size n. The best case is the cheapest such input, the worst case the most expensive, and the average case a weighted cost under a stated distribution. Linear search on [4, 1, 7] takes 1, 3 and 3 comparisons for targets 4, 7 and 9.
| Best successful case | 1 comparison, Theta(1): first item of a nonempty array matches |
|---|---|
| Worst case | n comparisons, Theta(n): target last or absent |
| Expected, target present | (n + 1) / 2 comparisons, Theta(n), if every position is equally likely |
| Absent target | n comparisons, all items checked before returning -1 |
| Auxiliary space | Theta(1) in the best, worst and expected cases |
This lesson assumes you can:
A performance case needs a condition in addition to a label such as “best” or “expected.”
For an array of fixed length :
We will count one specific operation: a comparison between an array value and target.
For linear search, we must also say whether the target is assumed to be present.
target in the array.target.For reference on input-dependent analysis and introductory algorithm analysis:
Use the same array for three searches.
| Index | 0 | 1 | 2 |
|---|---|---|---|
items | 4 | 1 | 7 |
So .
We will search this array three times:
target = 4target = 7target = 9Start at index 0. Compare each visited value with the target. Stop immediately when a match appears. If the search reaches the end without a match, return -1.
One array, three searches. Target 4 costs 1 comparison, target 7 costs 3, and target 9 costs 3 and returns -1. With n = 3 fixed, the input decides the work.
The target is present at index 0.
| Step | Current index | Comparison | Comparisons so far | Result |
|---|---|---|---|---|
| Start | 0 | — | 0 | continue |
| Inspect index 0 | 0 | 4 == 4 | 1 | return 0 |
This is the best successful case for . The first inspected value matches.
The target is present at the final index.
| Step | Current index | Comparison | Comparisons so far | Result |
|---|---|---|---|---|
| Start | 0 | — | 0 | continue |
| Inspect index 0 | 0 | 4 == 7 | 1 | no match |
| Inspect index 1 | 1 | 1 == 7 | 2 | no match |
| Inspect index 2 | 2 | 7 == 7 | 3 | return 2 |
This is a successful-search worst case for . The search must inspect every element before finding the target.
The target is absent.
| Step | Current index | Comparison | Comparisons so far | Result |
|---|---|---|---|---|
| Start | 0 | — | 0 | continue |
| Inspect index 0 | 0 | 4 == 9 | 1 | no match |
| Inspect index 1 | 1 | 1 == 9 | 2 | no match |
| Inspect index 2 | 2 | 7 == 9 | 3 | no match |
| End of array | — | — | 3 | return -1 |
An absent target requires the algorithm to rule out every array position.
Add an explicit assumption:
target is present.Then the possible comparison counts are:
| Target position | Probability | Comparisons |
|---|---|---|
| 0 | 1 | |
| 1 | 2 | |
| 2 | 3 |
The average is:
The average excludes absent-target inputs. It is an expectation only for the stated successful-position distribution.
Look at the moment just before inspecting index i.
Everything before i has already been checked. None of those earlier values matched target. A match at an earlier index would have caused the search to return before reaching index i.
The following fact remains true throughout the loop:
Invariant: Before inspecting index
i, all earlier indices have been compared withtargetand did not match; iftargetoccurs at an earlier checked index, the search would already have returned.
For example, before index 2 is inspected while searching for 7:
7 and did not match,7 and did not match,The invariant describes only the checked prefix. It does not establish whether the target occurs later in the array.
The invariant gives the steps.
-1.To measure work, keep a comparisons counter.
For a successful target at zero-based index :
So:
For expected successful-search cost, use a separate helper. Its contract must state that is positive and that every successful position is equally likely. Without those assumptions, is not a general expected-case result.
searchMetricsInput:
items: an array of valuestarget: the value to search forReturn: An object containing:
index: the first matching index, or -1 if no match existscomparisons: the number of items[i] == target comparisons performedMutation behavior: Does not modify items.
101 function searchMetrics(items, target):
202 comparisons <- 0
303
404 for i <- 0 to length(items) - 1:
505 comparisons <- comparisons + 1
606 if items[i] == target:
707 return { index: i, comparisons: comparisons }
808
909 return { index: -1, comparisons: comparisons }The loop boundary includes index length(items) - 1, the final valid index. If items is empty, the loop performs zero iterations.
expectedSuccessfulComparisonsInput:
n: a positive array lengthReturn: The expected number of equality comparisons for linear search when:
n positions is equally likely to contain it.Mutation behavior: Does not modify any input.
Precondition: n > 0.
101 function expectedSuccessfulComparisons(n):
202 require n > 0
303 return (n + 1) / 2The helper does not search an array. It computes the formula derived from the stated probability model.
Use items = [4, 1, 7].
Call:
1searchMetrics([4, 1, 7], 4)| Pseudocode line | State |
|---|---|
| 02 | comparisons <- 0 |
| 04 | Begin loop with i <- 0 |
| 05 | comparisons <- 1 |
| 06 | Test items[0] == 4, so test 4 == 4 |
| 07 | Condition is true; return { index: 0, comparisons: 1 } |
The loop ends because of the early return.
Call:
1searchMetrics([4, 1, 7], 7)| Pseudocode line | State |
|---|---|
| 02 | comparisons <- 0 |
| 04 | Begin loop with i <- 0 |
| 05 | comparisons <- 1 |
| 06 | Test items[0] == 7, so test 4 == 7; false |
| 04 | Next loop iteration: i <- 1 |
| 05 | comparisons <- 2 |
| 06 | Test items[1] == 7, so test 1 == 7; false |
| 04 | Next loop iteration: i <- 2 |
| 05 | comparisons <- 3 |
| 06 | Test items[2] == 7, so test 7 == 7; true |
| 07 | Return { index: 2, comparisons: 3 } |
Call:
1searchMetrics([4, 1, 7], 9)| Pseudocode line | State |
|---|---|
| 02 | comparisons <- 0 |
| 04 | Begin loop with i <- 0 |
| 05 | comparisons <- 1 |
| 06 | Test 4 == 9; false |
| 04 | Next loop iteration: i <- 1 |
| 05 | comparisons <- 2 |
| 06 | Test 1 == 9; false |
| 04 | Next loop iteration: i <- 2 |
| 05 | comparisons <- 3 |
| 06 | Test 7 == 9; false |
| 04 | No next index exists; the loop ends |
| 09 | Return { index: -1, comparisons: 3 } |
Call:
1expectedSuccessfulComparisons(3)| Pseudocode line | State |
|---|---|
| 02 | Check that 3 > 0; the precondition holds |
| 03 | Return (3 + 1) / 2, which is 2 |
The result applies only when the target is present and equally likely to occupy index 0, 1, or 2.
We will show that searchMetrics returns the first matching index when one exists, and returns -1 otherwise.
Before the first loop iteration, i = 0.
There are no indices before index 0. The invariant holds because there are no earlier indices to check.
Assume the invariant holds before inspecting index i.
The algorithm increments comparisons and compares items[i] with target.
i.
i is the first matching index.i has now been checked and shown not to match.
i + 1 has been checked and did not match.The loop either returns early or finishes after index .
i, the preservation argument shows that i is the first matching index.target is absent, so returning -1 is correct.The comparison count is correct because line 05 runs exactly once for each target equality comparison.
For expectedSuccessfulComparisons, the precondition says , and the probability model says every successful position is equally likely. The possible costs are , so returning their average, , matches that stated model.
Let be length(items). Count target equality comparisons.
If target is at zero-based index , the loop compares:
That is:
comparisons.
For nonempty arrays:
Best successful case:
k + 1 = 1
One comparison gives $\Theta(1)$ time. - **Worst successful case:** $k = n - 1$k + 1 = n
$n$ comparisons give $\Theta(n)$ time. ### Unsuccessful search If the target is absent, the algorithm must compare against every array item before returning `-1`.n
comparisons give $\Theta(n)$ time. The usual worst-case summary for linear search is $\Theta(n)$. The $\Theta(1)$ result applies only to the stated best successful condition: a nonempty array whose first item matches. ### Expected successful-search case Use this specific assumption: - the target is present, and - each of the $n$ positions is equally likely. The costs are $1, 2, \ldots, n$. Their average is:\frac{1 + 2 + \cdots + n}{n}
1 + 2 + \cdots + n = \frac{n(n+1)}{2}
\frac{n+1}{2}
The result is $\Theta(n)$. If positions have different probabilities, the average changes. For example, if index 0 has probability $0.9$, a uniform distribution does not describe that probability model. ### Auxiliary space The search keeps a fixed number of scalar variables: - `i` - `comparisons` - the returned fields It does not allocate storage proportional to $n$. Auxiliary space is therefore $\Theta(1)$ in the best, worst, and expected cases. ### Boundary inputs | Input | Return value | Comparisons | Case interpretation | |---|---|---:|---| | `items = []`, `target = 7` | `index = -1` | 0 | No successful target exists | | `items = [7]`, `target = 7` | `index = 0` | 1 | Best and worst successful cases coincide | | `items = [7]`, `target = 9` | `index = -1` | 1 | Unsuccessful search | | `items = [4, 1, 7]`, successful target uniformly positioned | expected count `2` | — | Excludes absent targets | ## Where Implementations Break ### Mistake 1: treating best case as the smallest input size **Incorrect assumption:** “Best case means the array has the smallest possible size.” Use the same-size inputs: ```text items = [4, 1, 7], target = 4 items = [4, 1, 7], target = 7 ``` Both arrays have $n = 3$. The first search takes 1 comparison, while the second takes 3 comparisons. **Wrong conclusion:** Both searches are the same case because $n = 3$. **Correction:** Compare costs among inputs of the same size. For linear search, the target’s position changes the number of comparisons. ### Mistake 2: assuming absence needs fewer comparisons **Incorrect assumption:** “If no index is returned, the search does less work.” Expose it with: ```text items = [4, 1, 7], target = 9 ``` The search checks: ```text 4 == 9 1 == 9 7 == 9 ``` **Wrong result:** Fewer than 3 comparisons. **Correction:** The algorithm can return `-1` only after checking every element. This input requires 3 comparisons. ### Mistake 3: averaging best and worst without a probability model **Incorrect assumption:** ```text expected comparisons <- (best comparisons + worst comparisons) / 2 ``` Suppose a successful target is at index 0 with probability $0.9$. The remaining positions are not equally likely in the same way as the uniform model. **Wrong result:** Always use:\frac{n+1}{2}
**Correction:** State probabilities first. An expected cost is a weighted average based on those probabilities. The formula $(n+1)/2$ requires equally likely successful positions. ### Mistake 4: reporting only the best-case bound **Incorrect assumption:** “Linear search is $O(1)$.” Expose it with: ```text items = [4, 1, 7], target = 9 ``` The algorithm makes 3 comparisons. More generally, an absent target requires $n$ comparisons. **Wrong result:** Label the algorithm $O(1)$ without a case condition. **Correction:** Attach the condition to the bound: - best successful case for a nonempty array: $\Theta(1)$, - worst case: $\Theta(n)$. ## Practice Implement: ```text searchMetrics(items, target) ``` It must return an object with: - `index` - `comparisons` It must handle: - a first-position match, - a final-position match, - an absent target, - an empty array. Then implement: ```text expectedSuccessfulComparisons(n) ``` It must return:\frac{n+1}{2}
for positive `n`, under a documented assumption that the target is present and uniformly distributed across the `n` possible positions. The executable tests cover first match, last match, absence, empty input, and expected values for $n = 1$ and $n = 3$.1def search_metrics(items, target):
2 comparisons = 0
3 for i in range(len(items)):
4 comparisons += 1
5 if items[i] == target:
6 return i, comparisons
7 return -1, comparisons
8
9def expected_successful_comparisons(n):
10 # assumes the target is present and every position is equally likely
11 assert n > 0
12 return (n + 1) / 2
13
14for items, target in [([4, 1, 7], 4), ([4, 1, 7], 7), ([4, 1, 7], 9), ([], 7)]:
15 index, comparisons = search_metrics(items, target)
16 print(f"n={len(items)} target={target} index={index} comparisons={comparisons}")
17for n in [1, 3]:
18 print(f"expected({n}) = {expected_successful_comparisons(n):.1f}")1public class Main {
2 static int[] searchMetrics(int[] items, int target) {
3 int comparisons = 0;
4 for (int i = 0; i < items.length; i++) {
5 comparisons++;
6 if (items[i] == target) return new int[]{i, comparisons};
7 }
8 return new int[]{-1, comparisons};
9 }
10
11 static double expectedSuccessfulComparisons(int n) {
12 // assumes the target is present and every position is equally likely
13 if (n <= 0) throw new IllegalArgumentException("n must be positive");
14 return (n + 1) / 2.0;
15 }
16
17 public static void main(String[] args) {
18 int[][] arrays = {{4, 1, 7}, {4, 1, 7}, {4, 1, 7}, {}};
19 int[] targets = {4, 7, 9, 7};
20 for (int c = 0; c < arrays.length; c++) {
21 int[] r = searchMetrics(arrays[c], targets[c]);
22 System.out.println("n=" + arrays[c].length + " target=" + targets[c]
23 + " index=" + r[0] + " comparisons=" + r[1]);
24 }
25 for (int n : new int[]{1, 3}) {
26 System.out.println("expected(" + n + ") = "
27 + String.format("%.1f", expectedSuccessfulComparisons(n)));
28 }
29 }
30}1#include <cstdio>
2#include <iostream>
3#include <utility>
4#include <vector>
5using namespace std;
6
7pair<int, int> searchMetrics(const vector<int>& items, int target) {
8 int comparisons = 0;
9 for (int i = 0; i < (int)items.size(); i++) {
10 comparisons++;
11 if (items[i] == target) return {i, comparisons};
12 }
13 return {-1, comparisons};
14}
15
16double expectedSuccessfulComparisons(int n) {
17 // assumes the target is present and every position is equally likely
18 return (n + 1) / 2.0;
19}
20
21int main() {
22 vector<vector<int>> arrays = {{4, 1, 7}, {4, 1, 7}, {4, 1, 7}, {}};
23 vector<int> targets = {4, 7, 9, 7};
24 for (size_t c = 0; c < arrays.size(); c++) {
25 pair<int, int> r = searchMetrics(arrays[c], targets[c]);
26 cout << "n=" << arrays[c].size() << " target=" << targets[c]
27 << " index=" << r.first << " comparisons=" << r.second << endl;
28 }
29 for (int n : {1, 3}) printf("expected(%d) = %.1f\n", n, expectedSuccessfulComparisons(n));
30}1function searchMetrics(items, target) {
2 let comparisons = 0;
3 for (let i = 0; i < items.length; i++) {
4 comparisons++;
5 if (items[i] === target) return { index: i, comparisons };
6 }
7 return { index: -1, comparisons };
8}
9
10function expectedSuccessfulComparisons(n) {
11 // assumes the target is present and every position is equally likely
12 if (n <= 0) throw new Error('n must be positive');
13 return (n + 1) / 2;
14}
15
16for (const [items, target] of [[[4, 1, 7], 4], [[4, 1, 7], 7], [[4, 1, 7], 9], [[], 7]]) {
17 const { index, comparisons } = searchMetrics(items, target);
18 console.log(`n=${items.length} target=${target} index=${index} comparisons=${comparisons}`);
19}
20for (const n of [1, 3]) console.log(`expected(${n}) = ${expectedSuccessfulComparisons(n).toFixed(1)}`);Neither. Big O bounds how a count grows; the case decides which input you count. The usual summary quotes the bound on the worst-case count, which for linear search is Theta(n).
It holds for every input of size n, so it is a guarantee. The best case is too optimistic to plan with: calling linear search O(1) fails on [4, 1, 7] with target 9, which takes 3 comparisons.
It needs two assumptions: the target is present and each position is equally likely. If index 0 holds the target with probability 0.9, the weighted average changes.
No. Returning -1 requires comparing every element, so [4, 1, 7] with target 9 takes 3 comparisons, the same as a target at the last index.
No. Compare costs among inputs of the same size. With [4, 1, 7], target 4 takes 1 comparison and target 7 takes 3, although n is 3 in both.