LESSON 215 OF 414 · BIG O NOTATION

Logarithms in Rust: O(log n) and Vec and String Method Costs

Watch the lesson

Next lesson

RUST · BIG O NOTATION

Introduction To Logarithm in Rust, explained

What a logarithm is

The base-2 logarithm of n answers one question: how many times can you halve n before you reach 1? For 8 the answer is 3 (8, 4, 2, 1), so log₂ 8 = 3. In Big O notation the base is dropped, because changing it only multiplies the result by a constant, so we write O(log n).

Logarithms matter because they grow so slowly. Doubling the input adds a single step. A loop that halves its range reaches the end quickly even for huge inputs:

fn halvings(mut n: u64) -> u32 {
    let mut steps = 0;
    while n > 1 {
        n /= 2;
        steps += 1;
    }
    steps
}

Integer division truncates, so the loop counts how many times n can be halved down to 1. The results are:

n = 8              -> 3
n = 1000           -> 9
n = 1000000        -> 19
n = 1000000000     -> 29

A billion elements need only 29 halvings. Rust has this calculation built in for integers: n.ilog2() returns the same numbers, the floor of the base-2 logarithm. It panics when n is 0, since the logarithm of zero is undefined.

Where logarithms show up

Whenever an algorithm throws away a fixed fraction of the remaining work at each step, the cost is logarithmic. The standard example is binary search on a sorted slice: look at the middle element, then continue in the half that can still contain the target.

fn search(sorted: &[i32], target: i32) -> (Option<usize>, u32) {
    let (mut lo, mut hi) = (0usize, sorted.len());
    let mut looks = 0;
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        looks += 1;
        if sorted[mid] == target {
            return (Some(mid), looks);
        }
        if sorted[mid] < target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    (None, looks)
}

The function returns the position (if found) and the number of elements it looked at. Searching for a value that is absent from the numbers 0 to 999 makes 10 looks. For the numbers 0 to 999999 it makes 20. A thousand times more data costs only ten more steps. The half-open range lo..hi means that hi - lo never goes below zero for a usize, and writing the midpoint as lo + (hi - lo) / 2 avoids overflow on very large ranges.

Costs of Vec and String methods

With logarithms in the vocabulary, here are the main groups of methods, by cost.

Constant time

Indexing, len(), is_empty(), first(), last() on a Vec or slice.
push() and pop() on a Vec (amortized), and swap(i, j).
len() on a String, which counts bytes.

Logarithmic time

binary_search() on a sorted slice.
push and pop on a BinaryHeap, while peek is O(1). After pushing 3, 9 and 1, peek() shows Some(9), the largest, and pop() removes and returns it.
Lookups and inserts in a BTreeMap or BTreeSet.

Linear time

contains(), iter().position(), iter().sum(), iter().max(), reverse(), clone().
insert(i, x) and remove(i) on a Vec, because later elements shift.
For strings, chars().count(), contains("..."), to_uppercase(), replace(...), and s.chars().rev().collect::<String>().

Linearithmic time

sort() and sort_unstable(), which are O(n log n): roughly log n levels of work, each touching all n elements.

Common mistakes

Using binary search on unsorted data. The O(log n) bound only holds because the order lets you discard half; on an unsorted vector the result is meaningless.
Forgetting the cost of sorting first. Sorting a vector and then binary-searching it once costs O(n log n), which is more than a single linear scan. Sorting pays off when you search many times.
Mixing up byte length and character count. For "héllo", len() is 6 and chars().count() is 5. The first is constant, the second linear.
Taking the logarithm of zero. 0u32.ilog2() panics, because ilog2 is only defined for positive integers.

Key takeaways

A logarithm counts how many times you can halve a number, and O(log n) grows by one step each time the input doubles.
Algorithms that discard a fraction of the data at every step, such as binary search, are logarithmic, and they need sorted data.
Know the cost of each Vec and String method before you call it inside a loop.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free