What time complexity measures
Time complexity describes how the work an algorithm does grows as its input grows. It does not measure seconds. A fast machine and a slow one disagree about seconds, but they agree on this: if you double the input, does the work stay the same, double, or quadruple?
We count basic operations, such as an addition, a comparison or reading one element, and express the count as a function of the input size, usually called n. Big O notation then keeps only the part of that function that dominates when n is large. Rust compiles to native code, so the actual running time is small, but the growth pattern is a property of the algorithm and is the same in every language.
Linear time: O(n)
An algorithm is linear when the work grows in step with the input. The classic example is a loop that visits each element once:
fn sum(nums: &[i32]) -> i64 {
let mut total = 0i64;
for &x in nums {
total += x as i64;
}
total
}The function takes a slice, &[i32], so it works with a Vec or an array without copying either. The loop body runs once per element. Counting the additions for slices holding the numbers from 0 up to n - 1 gives:
n = 10, additions = 10
n = 100, additions = 100
n = 1000, additions = 1000Ten times more input means ten times more additions. That is O(n). Searching an unsorted vector for a value, finding the maximum, counting the characters of a string with chars().count(), and copying a vector with clone() are all linear, because each has to look at every element in the worst case.
What Big O leaves out
Big O ignores constant factors. A function with two separate loops over the same data does about 2n operations, and a function with one loop does about n. Both are O(n). With n = 1000 and two loops that each add 1 to a counter, the counter ends at 2000, yet the growth is still linear: ten times the input still means ten times the work.
It also ignores lower-order terms. A loop that does n steps followed by a handful of fixed setup operations is O(n), because for large n the loop is all that matters.
Worst case
Big O usually describes the worst case. Looking for a value in a vector may find it at the first position, but if the value is last or absent, the whole vector is scanned. We say the search is O(n) because that is the guarantee that holds for every input of size n.
Linear time is not always a single loop
Some linear algorithms never write a loop. nums.iter().sum::<i32>() hides the loop inside the iterator, and it is still one pass over the data. Two loops one after the other add up to O(n + n), which is O(n). A loop that stops early is still O(n) in the worst case, because we cannot count on the early exit.
On the other hand, a loop is not automatically linear. A loop that halves the remaining range on each step, like binary search, takes far fewer steps than n. A loop with a fixed bound, such as for i in 0..100, does the same work for any input, so it is constant. And a loop nested inside another loop over the same data multiplies the work, which leads to quadratic time. Always ask how many times the body runs as a function of the input size.
Comparing it with other growth rates
| Notation | Name | What doubling the input does |
|---|---|---|
O(1) | Constant | No change |
O(log n) | Logarithmic | One extra step |
O(n) | Linear | Doubles the work |
O(n log n) | Linearithmic | A little more than doubles the work |
O(n²) | Quadratic | Quadruples the work |
For interview-style problems, the useful habit is to estimate the complexity before you write any code. If the input can have a million elements, an O(n) or O(n log n) solution is fine, while an O(n²) one is too slow.
Common mistakes
- Counting lines instead of growth. A long function with no loops can be
O(1), and a three-line function can beO(n²). - Forgetting hidden loops. Methods such as
contains,clone,to_vecandchars().count()walk the data. Calling one inside your own loop adds a factor ofn. - Keeping constants. Writing
O(2n)orO(n + 5)is not wrong in spirit, but the convention is to writeO(n). - Using
nfor two different sizes. If a function takes two slices of different lengths, say so: the cost might beO(a + b).
Key takeaways
- Time complexity is how the number of operations grows with the input size, not a measurement in seconds.
- Linear time,
O(n), means the work grows in proportion to the input, typically one pass over the data. - Drop constants and lower-order terms, and describe the worst case.
- Look for hidden loops in the standard library before you decide a line is cheap.
