Why the standard library's cost matters
Your own loops are easy to analyze, because you can see them. The calls into the standard library are harder: v.contains(&x) is one short expression, yet it hides a loop. If you put such a call inside your own loop, the costs multiply, so the complexity of your function depends on what each built-in does.
This lesson is a practice reading: for each common function, the cost to remember, and why.
Vec
| Operation | Time | Why |
|---|---|---|
v[i], v.len(), v.first(), v.last() | O(1) | Direct access by position |
v.push(x), v.pop() | O(1) amortized | Works at the end; an occasional reallocation is spread over many pushes |
v.insert(i, x), v.remove(i) | O(n) | The elements after position i shift |
v.swap_remove(i) | O(1) | Moves the last element into the gap; the order changes |
v.contains(&x), v.iter().position(...) | O(n) | Linear scan |
v.iter().sum(), .max(), .min(), .count() | O(n) | One pass over the elements |
v.reverse() | O(n) | Swaps pairs in place |
v.clone(), v.to_vec() | O(n) | Copies every element |
v.sort(), v.sort_unstable() | O(n log n) | Comparison sorting |
v.binary_search(&x) | O(log n) | Halves the range each step, and requires a sorted vector |
A quick run on [5, 3, 8, 1] shows the behaviour behind a few rows. After sort() the vector is [1, 3, 5, 8]. Then binary_search(&5) returns Ok(2), the position of the value, while binary_search(&4) returns Err(2), the position where 4 could be inserted to keep the order. Calling insert(0, 99) gives [99, 1, 3, 5, 8], and every old element moved one place. Calling swap_remove(0) on [1, 3, 5, 8] returns 1 and leaves [8, 3, 5], in constant time, because the last element filled the gap.
String and &str
s.len()isO(1): it returns the stored number of bytes. In"héllo"it is 6, sinceétakes two bytes in UTF-8.s.chars().count()isO(n): characters have different widths, so they must be decoded one by one. For the same string it is 5.s.push(c)isO(1)amortized, ands.push_str(t)is proportional to the length oft, also amortized.s.contains("ab"),s.find(...),s.to_uppercase(),s.to_string()ands.clone()are allO(n)or more.s.chars().rev().collect::<String>()isO(n).
Indexing a string by character position, like s[i], is not allowed in Rust, precisely because it could not be O(1) in UTF-8. To get the i-th character you use s.chars().nth(i), which is O(i). Inside a loop over all positions, that makes a quadratic algorithm, so collect the characters into a Vec<char> once, in O(n), and index that.
HashMap, HashSet and VecDeque
HashMapandHashSet:insert,get,removeandcontainsareO(1)on average. Iterating over all entries isO(n), and the order is not defined.VecDeque:push_back,push_front,pop_backandpop_frontare allO(1)amortized. It is the right choice for a queue; usingv.remove(0)on aVecas a queue costsO(n)each time.BTreeMap: operations areO(log n), and keys iterate in sorted order.
Using the table
When you write a function, multiply the cost of any built-in by the number of times you call it. Two examples show how it plays out:
- A loop over
nnumbers that callsseen.contains(&x)on aVecdoes up tonsteps per iteration, so the loop isO(n²). Replacing the vector with aHashSetmakes each checkO(1)on average and the loopO(n). - A function that calls
v.sort()once and then scans the vector isO(n log n) + O(n), which simplifies toO(n log n), the larger term.
Common mistakes
- Assuming
iter().sum()oriter().max()is free because it is one expression. - Calling
binary_searchon a vector that is not sorted: it still returns a result, but the result is unspecified, and theO(log n)guarantee tells you nothing about correctness. - Calling
remove(0)orinsert(0, x)in a loop, which is quadratic. - Treating
chars().count()likelen().
Key takeaways
- Access by index,
len, andpush/popat the end are constant time. - Searching, summing, copying and shifting are linear; sorting is
O(n log n); binary search isO(log n). - A built-in call inside a loop multiplies its cost by the number of iterations.
