Linear time, written O(n), describes work that grows proportionally with input size n. It describes growth, not elapsed time: a linear algorithm can be fast for small inputs and costly when inputs are large or the operation runs frequently. section 7.2
Searching an array
A search that checks array elements in order may need to inspect all n elements when the target is last or absent. Its worst-case work is therefore O(n). section 7.2
fn find(values: &[i32], number: i32) -> bool {
for i in 0..values.len() {
if values[i] == number {
return true;
}
}
false
}
The loop returns early on a match, but may visit every element before returning. section 7.2
Keep the case being measured explicit. Hash-table lookup averages O(1), yet collisions can require a linear scan and make its worst case O(n). Nor does a better growth class guarantee a faster result for a particular small input. section 7.2
To reduce repeated work and check the practical result:
- Cache previously calculated Fibonacci values with memoization, bringing the recursive calculation to linear time. section 7.7
- Compare that approach with an iterative implementation that advances through n loop steps. section 7.7
- Benchmark the alternatives with Criterion and cargo bench; use CPU profiling and a flame graph to locate remaining time-consuming calls. section 7.7
$ cargo bench fibonacci/recursive time: [157.39 ns 157.71 ns 158.06 ns] Found 10 outliers among 100 measurements (10.00%) 7 (7.00%) high mild 3 (3.00%) high severe fibonacci/memoization time: [43.891 ns 44.208 ns 44.637 ns] Found 6 outliers among 100 measurements (6.00%) 4 (4.00%) high mild 2 (2.00%) high severe fibonacci/iterative time: [5.0518 ns 5.0690 ns 5.0888 ns] Found 6 outliers among 100 measurements (6.00%) 4 (4.00%) high mild 2 (2.00%) high severe
At n = 10, these benchmark results put recursive, memoized, and iterative Fibonacci at roughly 157, 44, and 5 nanoseconds. They compare measured implementations at one input, not absolute speeds implied by big O. section 7.7 section 7.2
