What constant time means
An algorithm runs in constant time, written O(1), when the number of operations does not depend on the size of the input. The input can have ten elements or ten million, and the work is the same. Constant does not mean "one operation" or "fast". It means the count has an upper bound that never changes as the input grows.
fn first_plus_last(nums: &[i32]) -> i32 {
nums[0] + nums[nums.len() - 1]
}The function reads two elements and adds them. nums.len() returns a stored length, so it does not count anything, and indexing a slice jumps straight to the position. Called with [4, 8, 15, 16] it returns 20, and it would do the same few steps on a vector with a million elements. The function does panic on an empty slice, because index 0 does not exist, but that is a correctness question and does not change the complexity.
The guidelines for writing Big O
Big O is a simplified description, and a few rules turn an exact count into it.
Drop the constants
A function that does 3 operations and a function that does 300 operations, both independent of the input, are both O(1). Likewise, a loop that does 2n steps is O(n), not O(2n). Constants matter for real running time, but Big O describes how the cost scales.
Drop the lower-order terms
If a function does n + 50 operations, only n keeps growing, so the complexity is O(n). If it does n² + n, the answer is O(n²). In both cases the term that grows fastest decides the answer.
Take the worst case
When the work depends on the particular input, state the cost for the worst input of size n.
Add steps that run one after another, multiply steps that are nested
Two consecutive pieces of work add: O(n) + O(1) is O(n). A piece of work repeated inside a loop multiplies: n iterations of an O(n) body is O(n²).
A loop can still be constant
The word "loop" does not by itself mean growth. Look at what bounds the loop:
fn constant(v: &[i32]) -> i32 {
let mut total = 0;
for i in 0..100 {
total += i;
}
total + v[0]
}The loop runs exactly 100 times whatever the length of v, so the function is O(1). With v = [1] it returns 4951, and with a vector of a million ones it returns 4951 as well, after the same 100 iterations. The bound of the loop is a literal, not a function of the input.
A loop that depends on v.len() is a different story: it is O(n).
Constant-time operations in Rust
These operations take the same time however large the collection is:
- Arithmetic, comparisons and assignments on integers, floats,
boolandchar. - Reading or writing one element of a
Vecor an array by index:v[i]. len()andis_empty()on aVec, a slice or aString. For aString,len()is the number of bytes, which is stored, so it is constant. Counting characters withchars().count()is linear.pushandpopat the end of aVec. A push occasionally has to allocate a bigger buffer and move the elements, but spread over many pushes the average cost is constant. This is called amortized constant time.HashMapoperations such asinsert,getandcontains_key, on average. A pathological collision pattern can slow them down, but with the standard hasher that is not something you plan around.- Taking a sub-slice such as
&v[2..5], which only builds a pointer and a length.
The cost of an operation depends on what it touches. v.insert(0, x) looks like one call, yet it shifts every existing element one place to the right, so it is linear. v.contains(&x) and v.clone() are linear for the same reason.
Common mistakes
- Calling a function constant because its code is short. A single call to
sortorcontainsis not constant. - Assuming one line is one operation. The line decides nothing; what the call does with the data does.
- Forgetting that
O(1)only says the cost does not grow. A constant of a billion steps is stillO(1). - Treating amortized constant as worst-case constant. A single
pushcan be expensive, but any long run of pushes averages out.
Key takeaways
O(1)means the number of operations has a fixed bound that does not depend on the input size.- To simplify, drop constants and lower-order terms, keep the worst case, add sequential steps and multiply nested ones.
- A loop with a fixed count is constant, while a loop over
v.len()is linear. - Check what a standard library call does before assuming it is cheap.
