15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Time complexity describes how the work an algorithm does grows with the input size n. You choose one basic operation and count it instead of timing a clock, because a clock depends on hardware. Linear search does k + 1 equality tests when the target sits at index k, and n tests when it is absent.
| What you count | One basic operation, here the equality test items[i] == target |
|---|---|
| Input size n | The number of elements in the array, never an element's value |
| Target at index k | k + 1 comparisons, so 1 when it is first |
| Target absent | n comparisons, every element is checked |
| Phases in sequence | Counts add: 2 operations then 3 operations is 5 |
There are no prerequisites for this lesson.
We will measure an algorithm’s work by counting an abstract operation, not by using a clock. A clock depends on hardware, language, and other conditions. An operation count describes how the work changes when the input changes.
For this lesson:
n means the number of elements in items.
Our chosen basic operation is the equality test:
1items[i] == targetA comparison count is the number of times that equality test runs.
A fixed statement can have a count that does not change with input size. A scan through an array has work that can change when n changes.
When operations run one after another, their counts add. For example, if one phase does 2 selected operations and a later phase does 3, the sequence performs 5 selected operations. In linear search, an early return can prevent later comparisons from happening.
Consider this input:
1items = [4, 1, 7]
2index 0 1 2
3target = 7Here, n = 3 because items contains three elements. The values 4, 1, and 7 do not determine n; the array length does.
Our task is linear search:
0.target.-1.For this example, the target is at zero-based position 2.
An execution trace records the algorithm’s control-flow state in order. We will track:
i: the index currently being checkedcomparisons: how many equality tests have occurredLinear search for 7 in [4, 1, 7]: each equality test adds one to comparisons. The match at index 2 returns at once, after exactly 3 comparisons for n = 3.
| State | i | Comparison | comparisons | Result |
|---|---|---|---|---|
| State 0 | 0 | items[0] = 4 compared with 7 | 1 | No match |
| State 1 | 1 | items[1] = 1 compared with 7 | 2 | No match |
| State 2 | 2 | items[2] = 7 compared with 7 | 3 | Match; return 2 |
Write those states one at a time.
State 0
1i = 0
2items[0] == target
34 == 7 -> false
4comparisons = 1There is no match, so move to index 1.
State 1
1i = 1
2items[1] == target
31 == 7 -> false
4comparisons = 2There is still no match, so move to index 2.
State 2
1i = 2
2items[2] == target
37 == 7 -> true
4comparisons = 3
5return 2The return ends the search immediately. No later array positions are checked.
Before each comparison at index i, every earlier index has already been checked and did not contain target.
For example:
0, there are no earlier indices. The statement is true.1, index 0 has been checked and items[0] was not the target.2, indices 0 and 1 have been checked, and neither value was the target.The loop invariant is:
Before each comparison at index
i, every index from0throughi - 1has been checked and did not containtarget.
The invariant explains why returning i is valid. When items[i] == target, the current index matches, and every earlier index was already checked without matching. Therefore, i is the first matching index.
Start with the leftmost possible position, index 0.
At each index:
-1.The comparison count is not one fixed number for every input of the same length.
If the target occurs at zero-based position k:
0 through k are checked,k + 1.For the board example:
1k = 2
2comparisons = k + 1 = 2 + 1 = 3If the target is absent, every one of the n elements is checked. The count is then n.
linearSearch returns the first matching index, or -1 when no match exists.
comparisonCount follows the same left-to-right search path, but returns the number of equality comparisons performed instead.
Neither function changes items.
1Algorithm linearSearch(items, target)
2Input:
3 items: an array of elements
4 target: a value to search for
5Returns:
6 The first index i where items[i] equals target,
7 or -1 if target does not occur in items
8Mutation behavior:
9 Does not modify items
10
111. n <- length(items)
122. for i <- 0 to n - 1
133. if items[i] == target
144. return i
155. return -11Algorithm comparisonCount(items, target)
2Input:
3 items: an array of elements
4 target: a value to search for
5Returns:
6 The number of equality comparisons that linearSearch would perform
7Mutation behavior:
8 Does not modify items
9
101. n <- length(items)
112. comparisons <- 0
123. for i <- 0 to n - 1
134. comparisons <- comparisons + 1
145. if items[i] == target
156. return comparisons
167. return comparisonsThe loop boundary is n - 1, the final valid index. When n = 0, the range from 0 to -1 contains no indices, so the loop performs zero comparisons.
Use the original input again:
1items = [4, 1, 7]
2index 0 1 2
3target = 7linearSearch(items, target)| Pseudocode line | State |
|---|---|
| 1 | n <- length(items) gives n = 3. |
| 2 | Start loop with i = 0. |
| 3 | Test items[0] == target: 4 == 7 is false. |
| 2 | Continue loop with i = 1. |
| 3 | Test items[1] == target: 1 == 7 is false. |
| 2 | Continue loop with i = 2. |
| 3 | Test items[2] == target: 7 == 7 is true. |
| 4 | Return 2. The loop and function stop. |
comparisonCount(items, target)| Pseudocode line | State |
|---|---|
| 1 | n <- length(items) gives n = 3. |
| 2 | comparisons <- 0. |
| 3 | Start loop with i = 0. |
| 4 | comparisons <- 1. |
| 5 | Test 4 == 7: false. |
| 3 | Continue loop with i = 1. |
| 4 | comparisons <- 2. |
| 5 | Test 1 == 7: false. |
| 3 | Continue loop with i = 2. |
| 4 | comparisons <- 3. |
| 5 | Test 7 == 7: true. |
| 6 | Return 3. |
Exactly three equality comparisons occur before the return.
We show that linearSearch returns the first matching index, or -1 if no matching element exists.
Before the first loop iteration, i = 0.
There are no indices from 0 through -1. Therefore, it is true that every earlier index has been checked and did not contain target. The invariant holds before the first comparison.
Assume the invariant holds before checking index i.
If items[i] == target, the algorithm returns i.
i is the first matching index.If items[i] != target, the algorithm does not return.
i and shown that it does not contain target.i + 1, all indices from 0 through i have been checked and did not match.The loop either returns during a successful comparison or reaches the end of the array.
If it reaches the end, every index from 0 through n - 1 has been checked and did not contain target. Returning -1 is therefore correct.
For the worked input, the algorithm checks indices 0, 1, and 2. The equality comparison succeeds at index 2, so it returns 2 after exactly three comparisons.
Choose this basic operation:
1items[i] == targetNow count it.
If the target is at zero-based position k, the algorithm checks positions 0 through k.
k + 1.In the worked input, the target is at position 2.
2 + 1 = 3.If the target is absent, the algorithm checks all n elements.
n.If the target is the first element, the algorithm performs one comparison, even if the array has more elements.
The linear scan does work that grows linearly with the number of items when more items must be examined. Formal O notation is deferred.
The functions use a fixed number of extra variables:
nicomparisonCount, comparisonsThey do not create another array and do not modify items. Their auxiliary space is constant with respect to n.
| Input | Equality comparisons | Result |
|---|---|---|
items = [], target = 7 | 0 | not found, so return -1 |
items = [7], target = 7 | 1 | return index 0 |
items = [4, 1, 7], target = 4 | 1 | return index 0 |
items = [4, 1, 7], target = 9 | 3 | not found, so return -1 |
nIncorrect assumption
1comparisons = nExposing input
1items = [7, 1, 4]
2target = 7Wrong result
The assumption predicts 3 comparisons.
What actually happens
1items[0] == target
27 == 7The first comparison matches, so early return stops the search after 1 comparison.
Correction
The count depends on the target’s position:
k: k + 1 comparisons,n comparisons.Incorrect assumption
1n = 1000for:
1items = [1000, -2, 4]Wrong result
The assumption treats the value 1000 as the input size.
Correct state
1length(items) = 3
2n = 3Correction
n is the array length. It counts elements, not the magnitude or meaning of any element value.
Incorrect assumption
Count loop setup, index increments, comparisons, and returns together without stating what one unit of work means.
Exposing input
Use the trace:
1items = [4, 1, 7]
2target = 7Wrong result
Different line-counting choices can produce different totals, so the reported count does not clearly describe one operation.
Correction
Choose one basic operation and count it consistently. In this lesson, count only:
1items[i] == targetThe worked trace then has exactly three equality comparisons.
Implement:
1linearSearch(items, target)It must return the first matching index or -1.
Also implement:
1comparisonCount(items, target)It must return the number of equality comparisons performed by the same left-to-right search with early return.
Executable tests cover:
1def linear_search(items, target):
2 for i in range(len(items)):
3 if items[i] == target:
4 return i
5 return -1
6
7def comparison_count(items, target):
8 comparisons = 0
9 for i in range(len(items)):
10 comparisons += 1 # one equality test per visited index
11 if items[i] == target:
12 return comparisons
13 return comparisons
14
15cases = [([4, 1, 7], 7), ([4, 1, 7], 4), ([4, 1, 7], 9), ([], 7)]
16for items, target in cases:
17 print(f"n={len(items)} target={target} index={linear_search(items, target)} "
18 f"comparisons={comparison_count(items, target)}")1public class Main {
2 static int linearSearch(int[] items, int target) {
3 for (int i = 0; i < items.length; i++) {
4 if (items[i] == target) return i;
5 }
6 return -1;
7 }
8
9 static int comparisonCount(int[] items, int target) {
10 int comparisons = 0;
11 for (int i = 0; i < items.length; i++) {
12 comparisons++; // one equality test per visited index
13 if (items[i] == target) return comparisons;
14 }
15 return comparisons;
16 }
17
18 public static void main(String[] args) {
19 int[][] arrays = {{4, 1, 7}, {4, 1, 7}, {4, 1, 7}, {}};
20 int[] targets = {7, 4, 9, 7};
21 for (int c = 0; c < arrays.length; c++) {
22 int[] items = arrays[c];
23 int target = targets[c];
24 System.out.println("n=" + items.length + " target=" + target
25 + " index=" + linearSearch(items, target)
26 + " comparisons=" + comparisonCount(items, target));
27 }
28 }
29}1#include <iostream>
2#include <vector>
3using namespace std;
4
5int linearSearch(const vector<int>& items, int target) {
6 for (int i = 0; i < (int)items.size(); i++) {
7 if (items[i] == target) return i;
8 }
9 return -1;
10}
11
12int comparisonCount(const vector<int>& items, int target) {
13 int comparisons = 0;
14 for (int i = 0; i < (int)items.size(); i++) {
15 comparisons++; // one equality test per visited index
16 if (items[i] == target) return comparisons;
17 }
18 return comparisons;
19}
20
21int main() {
22 vector<vector<int>> arrays = {{4, 1, 7}, {4, 1, 7}, {4, 1, 7}, {}};
23 vector<int> targets = {7, 4, 9, 7};
24 for (size_t c = 0; c < arrays.size(); c++) {
25 cout << "n=" << arrays[c].size() << " target=" << targets[c]
26 << " index=" << linearSearch(arrays[c], targets[c])
27 << " comparisons=" << comparisonCount(arrays[c], targets[c]) << endl;
28 }
29}1function linearSearch(items, target) {
2 for (let i = 0; i < items.length; i++) {
3 if (items[i] === target) return i;
4 }
5 return -1;
6}
7
8function comparisonCount(items, target) {
9 let comparisons = 0;
10 for (let i = 0; i < items.length; i++) {
11 comparisons++; // one equality test per visited index
12 if (items[i] === target) return comparisons;
13 }
14 return comparisons;
15}
16
17const cases = [[[4, 1, 7], 7], [[4, 1, 7], 4], [[4, 1, 7], 9], [[], 7]];
18for (const [items, target] of cases) {
19 console.log(`n=${items.length} target=${target} index=${linearSearch(items, target)} ` +
20 `comparisons=${comparisonCount(items, target)}`);
21}No. A clock depends on hardware, language and other conditions. An operation count describes how the work changes when the input changes, so it stays the same on every machine.
No. Time complexity is the work count as a function of n. Big O is the notation that labels how fast that count can grow. Linear search with 3 items and 3 comparisons is the count; "linear" is the label.
O(1) means the count does not depend on n: linear search for a first-element target makes 1 comparison on any array. O(n) means the count grows in step with n: an absent target costs n comparisons.
Define n, pick one basic operation, then count how often it runs. Sequential phases add their counts. Check the early exits too: [4, 1, 7] with target 7 costs 3 comparisons, but target 4 costs 1.
No. n is the array length. For items = [1000, -2, 4], n is 3, because the length counts elements and ignores their magnitude.