Rust for Algorithmic Problem-Solving

Big-O Analysis in Rust

Big-O analysis characterizes how an algorithm's execution time and memory consumption scale as the input size $N$ grows. In Rust, writing algorithms that meet strict latency budgets or 1.0-second competitive programming time limits requires knowing both the input-size-to-complexity budget and the hidden asymptotic costs of standard library methods.

Rule of Thumb for a 1.0-Second Time Budget in Release Rust (~10^8 Simple Ops/Sec):

  Input Size `N`          Maximum Feasible Time Complexity      Typical Algorithms
  ----------------------------------------------------------------------------------------------
  N <= 11                 O(N!)                                 Permutations / Backtracking
  N <= 20                 O(2^N) or O(N * 2^N)                  Bitmask DP / Meet-in-the-Middle
  N <= 500                O(N^3)                                Floyd-Warshall / Matrix Mul
  N <= 5,000              O(N^2)                                Quadratic DP / All-Pairs
  N <= 200,000            O(N log N) or O(N log^2 N)            Sorting, Dijkstra, Segment Tree
  N <= 5,000,000          O(N)                                  Sliding Window, Hashing, BFS/DFS
  N >= 10^9               O(log N) or O(sqrt(N)) or O(1)        Binary Search, Math, Matrix Exp

Hidden $O(n)$ Traps in Standard Rust Methods (That Turn $O(n)$ Loops into $O(n^2)$!)

One of the most common causes of unexpected slowdowns in Rust is calling an innocent-looking $O(n)$ method inside an $O(n)$ loop:

Hidden $O(n)$ Trap Inside a Loop Actual Complexity in $N$-Step Loop Fast $O(1)$ / $O(n)$ Total Replacement
s.chars().nth(i) $O(n^2)$! (Walks UTF-8 from byte 0 every call) Index s.as_bytes()[i] ($O(1)$) or collect Vec<char> once upfront!
vec.remove(0) / vec.insert(0, x) $O(n^2)$! (Shifts all $n$ elements on every call) Use VecDeque::pop_front() / push_front() ($O(1)$) or vec.swap_remove(i) ($O(1)$)!
vec.contains(&x) $O(n^2)$! (Linear scan on every check) Use HashSet::contains(&x) ($O(1)$) or slice.binary_search(&x) ($O(\log n)$)!
acc = format!("{acc}{piece}") $O(n^2)$! (Allocates & copies entire prefix every step) Use acc.push_str(piece) ($O(1)$ amortized) or write!(&mut acc, ...)!
Passing vec.clone() into recursive calls $O(n \cdot \text{calls})$! (Deep-copies entire vector at every node) Pass a shared slice &[T] (or &mut Vec<T> with push + pop backtracking)!

Demonstrating $O(n)$ In-Place Backtracking vs $O(n \cdot 2^n)$ Cloning

When recursion explores subsets or paths, mutating a single shared &mut Vec<T> with path.push(x) before recursing and path.pop() after returning avoids allocating a new Vec at every node of the recursion tree:

/// Generates all subsets of `nums` whose sum equals `target`, mutating a single
/// `current_path` buffer in-place (`push` + `pop`) so zero heap allocations occur on dead-end branches!
pub fn find_subsets_summing_to(nums: &[i64], target: i64) -> Vec<Vec<i64>> {
    let mut results = Vec::new();
    let mut current_path = Vec::with_capacity(nums.len());

    fn backtrack(
        idx: usize,
        running_sum: i64,
        nums: &[i64],
        target: i64,
        path: &mut Vec<i64>,
        results: &mut Vec<Vec<i64>>,
    ) {
        if idx == nums.len() {
            if running_sum == target {
                results.push(path.clone()); // Only clone when a valid answer is found!
            }
            return;
        }

        // Branch 1: Exclude `nums[idx]`
        backtrack(idx + 1, running_sum, nums, target, path, results);

        // Branch 2: Include `nums[idx]` using in-place push + pop
        path.push(nums[idx]);
        backtrack(
            idx + 1,
            running_sum + nums[idx],
            nums,
            target,
            path,
            results,
        );
        path.pop(); // Restore `path` in O(1) time!
    }

    backtrack(0, 0, nums, target, &mut current_path, &mut results);
    results
}

fn main() {
    let subsets = find_subsets_summing_to(&[2, 4, 6, 10], 10);
    assert_eq!(subsets, vec![vec![10], vec![4, 6]]);
    println!("Subsets summing to 10: {subsets:?}");
}

Subsets summing to 10: [[10], [4, 6]]