Rust's standard library publishes a cost table. Vec indexing is O(1), push is amortized O(1), and insert or remove at index i is O(n - i). HashMap get, insert and remove are expected O(1), BTreeMap's are O(log n), and BinaryHeap pop is O(log n). sort is stable and sort_unstable is not, and both are O(n * log(n)) in the worst case.
Where these figures come from
The figures below come from the std::collections module, which has a table of costs, and from the documentation of each type and method, which adds worst cases and conditions. All were read on November 12, 2026, in the documentation for Rust 1.100.0.
The table marks two kinds of cost, and the difference is worth saying in an interview. A cost with * is amortized: "an individual operation may be slower or faster due to the sporadic nature of collection resizing," but the average over many operations approaches it. A cost with ~ is expected: "it is theoretically possible, though very unlikely, for HashMap to experience significantly worse performance than the expected cost." n is the collection's size, i is an index, and m is the size of a second collection.
Vec
From the collections table and the Vec methods. The front of a Vec is the expensive end.
| Operation | Cost | Note |
|---|---|---|
v[i], v.get(i) | O(1) | |
v.push(x) | O(1) amortized | If the push exceeds the capacity, "O(capacity) time is taken to copy the vector's elements to a larger allocation." |
v.pop() | O(1) | |
v.insert(i, x) | O(n - i) amortized | The method's note: "Takes O(Vec::len) time" in the worst case, at index 0. |
v.remove(i) | O(n - i) | Its note: it "has a worst-case performance of O(n)." The docs suggest VecDeque::pop_front for the front. |
v.swap_remove(i) | O(1) | "Does not preserve ordering of the remaining elements." |
v.contains(&x) | O(n) | The docs point to binary_search for a sorted slice. |
v.append(&mut other) | O(m) amortized | m is the length of other. |
v.split_off(i) | O(n - i) |
VecDeque
VecDeque is "a double-ended queue implemented with a growable ring buffer." Its row in the table gives insert and remove at index i as O(min(i, n - i)), so both ends are cheap and the middle is the slow part. That makes it the type for a queue.
| Operation | Cost | Note |
|---|---|---|
d[i], d.get(i) | O(1) | |
d.insert(i, x) | O(min(i, n - i)) amortized | At either end, i or n - i is 0, which is how push_front and push_back stay cheap. |
d.remove(i) | O(min(i, n - i)) | Again cheapest at the ends: pop_front, pop_back. |
d.swap_remove_back(i), d.swap_remove_front(i) | O(1) | "Does not preserve ordering." |
d.contains(&x) | O(n) |
HashMap and HashSet
HashMap is "a hash map implemented with quadratic probing and SIMD lookup," a port of Google's SwissTable. Its default hasher is SipHash 1-3, chosen for "resistance against HashDoS attacks" over raw speed. The collections page adds: "For Sets, all operations have the cost of the equivalent Map operation," so HashSet costs the same.
| Operation | Cost | Note |
|---|---|---|
m.get(&k) | O(1) expected | |
m.insert(k, v) | O(1) expected, amortized | Both marks: it depends on hashing and on resizing. |
m.remove(&k) | O(1) expected | |
| Iterating over keys or values | O(capacity) | "In the current implementation, iterating over keys takes O(capacity) time instead of O(len) because it internally visits empty buckets too." |
That last row matters together with another line on the collections page: "Rust's collections never automatically shrink." A map that grew large and then had most entries removed still iterates over its full capacity until you call shrink_to_fit.
BTreeMap and BTreeSet
BTreeMap is "an ordered map based on a B-Tree." Use it when you need keys in order or a range of them. Its page explains that each node currently searches its keys linearly, so "searching for a random element is expected to take B * log(n) comparisons," with the note that "in practice, however, performance is excellent."
| Operation | Cost | Note |
|---|---|---|
m.get(&k) | O(log(n)) | |
m.insert(k, v) | O(log(n)) | Not marked amortized in the table. |
m.remove(&k) | O(log(n)) | |
m.range(a..b) | O(log(n)) | The table's figure. Iterating over what it returns costs extra. |
m.append(&mut other) | O(n + m) | m is the size of other. |
BinaryHeap
BinaryHeap is a max-heap. For a min-heap the docs suggest wrapping items in std::cmp::Reverse. Its page has its own small table, and its push cost is the most carefully qualified in the standard library.
| Operation | Cost | Note |
|---|---|---|
h.peek() | O(1) | "Cost is O(1) in the worst case." |
h.push(x) | O(1) expected | Averaged over orderings. Pushing in ascending order costs O(log(n)) amortized, and one push that resizes is O(n). |
h.pop() | O(log(n)) | "The worst case cost of pop on a heap containing n elements is O(log(n))." |
BinaryHeap::from(vec) | O(n) | "This conversion happens in-place." |
Vec::from(heap) | O(1) | "Requires no data movement or allocation." |
sort and sort_unstable
Both are methods on slices, so they work on a Vec too. Their documentation gives the guarantee and, separately, the current algorithm.
| Method | Cost | Stable | Memory |
|---|---|---|---|
v.sort() | O(n * log(n)) worst case | Yes | Allocates: nothing for short slices, self.len() for medium ones, and beyond that it "clamps at self.len() / 2." |
v.sort_unstable() | O(n * log(n)) worst case | No | "In-place (i.e., does not allocate)." |
v.select_nth_unstable(k) | O(n) | No | Puts the kth element in its sorted place. In-place. |
v.binary_search(&x) | Not stated | n/a | "If the slice is not sorted, the returned result is unspecified and meaningless." |
The current sort is based on driftsort and sort_unstable on ipnsort. Both docs say they achieve "linear time on fully sorted and reversed inputs," and an expected O(n * log(k)) on inputs with k distinct elements. The docs prefer sort_unstable when applicable, since it is "generally faster than stable sorting" and does not allocate, except on partially sorted data.
String
String is UTF-8, and its page explains why you cannot index it by character: "only byte indices would provide constant time indexing." Getting the ith character with s.chars().nth(i) walks the string from the start.
Building a string is cheap if you do it the Rust way. The + operator "consumes the String on the left-hand side and re-uses its buffer," which the docs say avoids the "O(n^2) running time when building an n-byte string by repeated concatenation."
Common interview traps
Each line here is a choice from the tables above, with the slow version beside the fast one.
Rust
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashSet, VecDeque};
// 1. Using a Vec as a queue: remove(0) shifts everything, O(n) per call.
fn drain_slow(mut tasks: Vec<u32>) -> Vec<u32> {
let mut order = Vec::new();
while !tasks.is_empty() {
order.push(tasks.remove(0)); // O(n)
}
order
}
fn drain(tasks: Vec<u32>) -> Vec<u32> {
let mut queue: VecDeque<u32> = tasks.into();
let mut order = Vec::with_capacity(queue.len());
while let Some(t) = queue.pop_front() { // cheap at either end
order.push(t);
}
order
}
// 2. contains() on a Vec inside a loop is O(n) per check.
fn first_seen(items: &[u32]) -> Vec<u32> {
let mut seen = HashSet::new();
items.iter().copied().filter(|x| seen.insert(*x)).collect()
}
// 3. BinaryHeap is a max-heap. Reverse turns it into a min-heap,
// here keeping the k largest values in O(n log k).
fn top_k(values: &[i64], k: usize) -> Vec<i64> {
let mut heap = BinaryHeap::with_capacity(k + 1);
for &v in values {
heap.push(Reverse(v));
if heap.len() > k {
heap.pop(); // drops the smallest
}
}
heap.into_iter().map(|Reverse(v)| v).collect()
}
// 4. Order doesn't matter? swap_remove is O(1) where remove is O(n).
fn remove_fast(v: &mut Vec<u32>, i: usize) -> u32 {
v.swap_remove(i)
}Two more need no code: indexing a String by character position (walk it with chars, or work in bytes when the input is ASCII), and reaching for sort when sort_unstable would do, which allocates for no benefit when equal elements are indistinguishable.
How to say it out loud
I'll keep the visited set in a HashSet, which the standard library documents as expected O(1) per insert and lookup, and the queue in a VecDeque, since popping from the front of a Vec is O(n). So the search is O(V + E) expected time and O(V) space. If I needed the keys in order, I'd use a BTreeMap and pay O(log n) per operation instead.
I'll use sort_unstable here. The values are plain integers, so stability can't change the result, and it sorts in place in O(n log n) worst case without allocating.
Saying "expected" for the hash map and "amortized" for push is the precision the Rust docs model for you. Practice it in a coding mock interview, and see the Big O cheat sheet for the structures in general.
What the docs do not state
These have no figure in the pages read for this guide, so they have no cost above:
binary_searchon a slice: the docs describe the result but give no Big O.VecDeque::push_front,push_back,pop_frontandpop_back: no figure on the methods themselves. The cost above comes from the table's insert and remove row at either end.String::push_strandchars().nth: no figure, only the explanation of why indexing by character is not constant time.- A worst case for HashMap: the docs say only that it is "theoretically possible, though very unlikely" to be much worse than expected.
Complexity by language
Each language page takes its figures from that language's own documentation, cites it, and says what the documentation leaves out. TypeScript runs as JavaScript, so its costs are on the JavaScript page.
For the structures and algorithms themselves, see the Big O cheat sheet and sorting algorithm complexity.
Frequently asked questions
Is HashMap insert O(1) in Rust?
Expected O(1), amortized. The standard library's cost table marks HashMap insert with both: expected because of hashing, and amortized because of resizing. The docs say it is theoretically possible, though very unlikely, to be significantly worse than the expected cost.
Is Vec remove O(n) in Rust?
Yes. Removing at index i is O(n - i), because every later element shifts left, and the method notes a worst case of O(n). Use swap_remove for O(1) when order does not matter, or a VecDeque, whose ends are cheap, for a queue.
Is BinaryHeap a min-heap or a max-heap in Rust?
A max-heap. For a min-heap, wrap the items in std::cmp::Reverse or give them a custom Ord. Peek is O(1), pop is O(log(n)), and push is expected O(1) when items arrive in no particular order.
What is the difference between sort and sort_unstable in Rust?
sort is stable and may allocate extra memory, and sort_unstable may reorder equal elements but sorts in place without allocating. Both are O(n * log(n)) in the worst case. The docs prefer sort_unstable when it applies, since it is generally faster.