Data structures & algorithms / Lesson 1
Understand the cost of code
Count the work in a Go program, compare growth rates, and separate running time from extra memory.
You have eight job IDs and need to find one. Reading them in order seems reasonable. Now imagine checking every pair of IDs for duplicates. Both tasks fit in a few lines of Go, but adding more IDs affects them very differently.
The useful first question is: how much work does this code do as the input grows? We can answer that before choosing a faster machine or running a benchmark.
Choose a unit of work
Let n mean the number of integers in the input slice. Count one operation each time the program compares two integer values with ==. This gives us a clear, repeatable model. We treat a comparison of these fixed-width integers as constant work.
We are not counting loop conditions, increments, allocation, or printing. Those operations still happen. The chosen count helps us understand the main repeated work; it is not an instruction count or an elapsed-time measurement. Comparing long strings, calling a service, and comparing integers can have different costs.
Follow a linear search
linearSearch reads one value at a time and returns the first matching index. Indices start at zero. The function also returns its comparison count, so we can check the reasoning directly.
For [0 1 2 3 4 5 6 7], compare the target with the value 0.
Target 0 returns index 0 after one comparison.
Target -1 is absent. All eight values are compared, then the function returns -1.
For a nonempty slice, the best case takes one comparison. The worst case takes n: the target is last or absent. An empty slice takes zero comparisons. A match at index k takes k + 1. These are exact counts for this implementation.
Count unique pairs
countEqualPairs answers a different question: how many unordered pairs of positions contain equal values? It checks every pair, even after finding a match. Starting the inner index at i + 1 avoids comparing a position with itself and avoids checking the same pair in both orders.
For four positions, the pairs are (0,1), (0,2), (0,3), (1,2), (1,3), and (2,3). Position 0 contributes three checks, position 1 contributes two, and position 2 contributes one. In general:
(n − 1) + (n − 2) + … + 1 = n(n − 1) / 2.
There are zero checks when n is zero or one. For any fixed length, all-distinct values and all-equal values require the same number of checks here. They produce different match counts. An implementation that returns after the first duplicate would need a separate best-case analysis.
Describe growth without predicting seconds
| Input size n | Missing linear search | Exhaustive pair checks |
|---|---|---|
| 8 | 8 | 28 |
| 64 | 64 | 2,016 |
| 1,024 | 1,024 | 523,776 |
Big O is an upper growth bound. Saying a cost is O(n) means that, beyond some input size, it is at most a constant multiple of n. Theta is a tight growth bound: both an upper and a lower constant multiple apply. Constants and smaller terms do not change that classification. [1]
The search’s worst-case comparison count is Θ(n); its best case for nonempty inputs is Θ(1). Exhaustive pair checking is Θ(n²). Big O does not itself mean “worst case.” Name the case, then describe its growth. The search’s worst case is also technically O(n²), but that looser bound hides useful information.
Two nested loops do not automatically mean quadratic work. An outer loop that runs n times with an inner loop that always runs three times does 3n iterations: Θ(n). Count the total iterations instead of counting the indentation levels.
Account for space separately
The input holds n integers, so its storage grows linearly. Both functions use only a fixed number of indices, values, and counters beyond that input: Θ(1) auxiliary space. Neither stores the pairs it checks. If it collected every pair into an output slice, that output could require quadratic storage.
The demonstration allocates each input before calling the functions. That setup is separate from their auxiliary-space analysis. Always state whether a space claim includes input, output, or only temporary working storage.
Run the Go example
Save main.go and main_test.go together in an empty directory. The module setting lets you run these standalone files without creating a module.
go run main.go
GO111MODULE=off go test -v
GO111MODULE=off go vetThe complete source uses ordinary slice iteration. Go defines that iteration in its specification. [2] The fixed example sizes keep the integer counters in range; this is not an arbitrary-size counting API.
package main
import "fmt"
func linearSearch(values []int, target int) (index, comparisons int) {
for index, value := range values {
comparisons++
if value == target {
return index, comparisons
}
}
return -1, comparisons
}
func countEqualPairs(values []int) (pairs, comparisons int) {
for i := 0; i < len(values); i++ {
for j := i + 1; j < len(values); j++ {
comparisons++
if values[i] == values[j] {
pairs++
}
}
}
return pairs, comparisons
}
func main() {
values := []int{0, 1, 2, 3, 4, 5, 6, 7}
index, comparisons := linearSearch(values, 0)
fmt.Printf("first: index=%d comparisons=%d\n", index, comparisons)
index, comparisons = linearSearch(values, -1)
fmt.Printf("missing: index=%d comparisons=%d\n", index, comparisons)
// These small inputs keep all counters within the range of int.
for _, size := range []int{8, 64, 1024} {
input := make([]int, size)
for i := range input {
input[i] = i
}
_, linearComparisons := linearSearch(input, -1)
pairs, pairComparisons := countEqualPairs(input)
fmt.Printf("n=%d linear=%d pair-checks=%d matches=%d\n",
size, linearComparisons, pairComparisons, pairs)
}
}Expected output:
first: index=0 comparisons=1
missing: index=-1 comparisons=8
n=8 linear=8 pair-checks=28 matches=0
n=64 linear=64 pair-checks=2016 matches=0
n=1024 linear=1024 pair-checks=523776 matches=0Check your understanding
1. A match near the start
A 100-element slice first contains the target at index 2. How many equality comparisons does this search perform?
Reveal answer: a match near the start
Three. It checks indices 0, 1, and 2, then returns. This particular run does not reach the worst case.
2. Duplicate values
For [7 7 7 7], how many pair checks and matching pairs does the example produce?
Reveal answer: duplicate values
Six checks and six matching pairs. Every unordered pair matches, and the function still examines all pairs.
3. Two complete passes
A function scans all n values, then scans all n values again. What is its total iteration count and tight growth bound?
Reveal answer: two complete passes
The total is 2n, so the bound is Θ(n). Separate passes add their work. They do not multiply it.
Primary references
- MIT 6.006, Recitation 1: Asymptotic Complexity — upper, lower, and tight growth bounds.
- Go specification: range clauses — iteration over a slice.