Two operations that look cheap
Taking a piece of a collection and joining two collections are everyday operations, and their cost depends on one question: does the operation copy the data, or does it only point at it? In Rust the answer is visible in the types, which makes the complexity easy to read once you know the rule.
Slicing
A slice expression such as &v[2..5] does not create a new vector. It creates a borrowed view, a pointer into the original data plus a length. Building that view takes constant time, whatever the size of the vector and the length of the range.
let v: Vec<i32> = (0..10).collect();
let part = &v[2..5];
println!("{:?}", part);[2, 3, 4]The pointer of part is exactly the address of the element at index 2 in v: no element was copied. The same holds for strings: with s = String::from("hello world"), the expression &s[6..] is a &str holding world, and it points inside s. So passing slices to functions is O(1), and recursive algorithms that work on &v[1..] do not pay a copying cost at each call.
Copying happens only when you ask for it:
part.to_vec()allocates a newVecand copies the elements:O(k)forkelements.w.to_string()orString::from(w)on a&strcopies the bytes:O(k).v.clone()copies the whole vector:O(n).
Anything you then do with the slice also costs time in proportion to its length. Summing &v[a..b] takes O(b - a), even though creating the slice was free.
Slicing can panic
An out-of-range slice such as &v[2..20] on a 10-element vector panics. For strings there is a second rule: the range is in bytes, and both ends must fall on character boundaries. In "é", which takes two bytes, position 1 is in the middle of the character, so is_char_boundary(1) is false and &s[..1] would panic. When the text may contain non-ASCII characters, work with chars() or collect them into a Vec<char>.
Concatenation
Joining two sequences has to produce a sequence holding both, so its cost is proportional to the amount of data written.
a + &bon strings consumesaand appends the bytes ofbto it. The cost isO(len of b)amortized, becausea's buffer is reused. Afterlet c = a + &b;witha = "ab"andb = "cd",cis"abcd",bis still usable, andahas been moved and can no longer be used.s.push_str(t)is the same append without a new variable, ands.push(c)appends one character inO(1)amortized.format!("{}{}", a, b)builds a new string and copies both parts:O(len a + len b).v.extend_from_slice(&w)appends a slice to a vector inO(len of w)amortized;vec_of_vecs.concat()allocates a new vector and copies every element once. For[[1, 2], [3]]it produces[1, 2, 3].
Building a result in a loop
The loop below appends the text of the numbers 0 to 4 and ends with "01234":
let mut out = String::new();
for i in 0..5 {
out.push_str(&i.to_string());
}Appending to one growing String is linear overall: the total work is proportional to the total number of bytes written. The pattern to avoid is creating a fresh string on every iteration that copies the whole result so far, for example out = format!("{}{}", out, i). The k-th iteration then copies about k characters, and the total is 1 + 2 + ... + n, which is O(n²). The same trap exists for vectors: result = [result, piece].concat() inside a loop is quadratic, while result.extend_from_slice(&piece) is linear overall.
Summary table
| Operation | Time |
|---|---|
&v[a..b], &s[a..b] | O(1) |
v[a..b].to_vec(), s[a..b].to_string() | O(b - a) |
s.push(c) | O(1) amortized |
s.push_str(t), a + &b | O(len t), O(len b) amortized |
format!("{}{}", a, b) | O(len a + len b) |
v.extend_from_slice(&w) | O(len w) amortized |
[x, y].concat() | O(total length) |
Common mistakes
- Believing that a slice is a copy, and therefore avoiding slices in recursion. The slice itself is free; the copy appears only with
to_vec(),to_string()orclone(). - Calling
to_vec()orto_string()on a slice inside a loop "just to be safe", which turns a linear algorithm into a quadratic one. - Slicing strings with byte positions that split a multi-byte character.
- Rebuilding a string or vector from scratch on every loop iteration instead of appending to it.
Key takeaways
- A slice is a view: creating it is
O(1), and copying it out costs time proportional to its length. - Concatenation costs time proportional to the data appended when you reuse the buffer, and to everything copied when you build a new value.
- Append to one growing
StringorVecrather than rebuilding it in a loop.
