A few years ago, I was reviewing a PR from a developer who had written a function to filter out duplicate usernames from a massive CSV import. On his local machine, with a test file of about 500 names, the code ran in a blink. He felt great. But the moment we pushed it to the staging environment and fed it a real production dataset of 100,000 users, the server basically froze. The CPU spiked to 100%, and the request timed out. The culprit? He had used a nested loop—for every name in the list, he scanned the entire "already seen" list to see if it existed. It was a classic case of $O(n^2)$ complexity hitting a wall.

This is why we talk about Big-O notation. It isn't just academic fluff for computer science interviews; it's the language we use to describe how an algorithm's resource requirements grow as the input size grows. When I talk about "time complexity," I'm not talking about seconds or milliseconds—because those change depending on whether you're running on a MacBook M3 or a ten-year-old ThinkPad. Instead, we're talking about the rate of growth.

The Growth Curve of Common Rust Operations

In Rust, you'll encounter a few common complexity classes daily. The most efficient is $O(1)$, or constant time. No matter if your Vec has ten elements or ten million, accessing an element by index—like my_vec[42]—takes the same amount of time. The CPU just calculates a memory offset and jumps there.

Then there's $O(n)$, linear time. If you're searching for a specific value in a Vec using .iter().find(), you might get lucky and find it first, but in the worst case, you have to look at every single element. If the list doubles in size, the time it takes to search doubles. It's a fair trade-off, but it starts to hurt when $n$ gets truly huge.

The real trouble starts with $O(n^2)$, quadratic time. This usually happens when you nest a loop inside another loop over the same collection. If you have 1,000 items, you're doing 1,000,000 operations. If you move to 100,000 items, you're suddenly looking at 10 billion operations. That's how my colleague's import script crashed.

// O(n^2) - The "Danger Zone"
fn has_duplicates(list: &[&str]) -> bool {
    for i in 0..list.len() {
        for j in i + 1..list.len() {
            if list[i] == list[j] {
                return true;
            }
        }
    }
    false
}

Leveraging Collections for Better Complexity

The secret to fixing $O(n^2)$ problems is usually trading a bit of memory (space complexity) for speed (time complexity). In Rust, this almost always means swapping a Vec for a HashSet or a HashMap. While adding an item to a Vec is $O(1)$, checking if a Vec contains an item is $O(n)$. However, checking if a HashSet contains an item is $O(1)$ on average.

By using a HashSet, we can turn that nested loop into a single pass. We iterate through the list once, checking the set and inserting the value. This transforms the operation from $O(n^2)$ to $O(n)$. The difference is staggering: for 100,000 items, we go from 10 billion checks to just 100,000.

use std::collections::HashSet;

// O(n) - Much more scalable
fn has_duplicates_fast(list: &[&str]) -> bool {
    let mut seen = HashSet::new();
    for item in list {
        if !seen.insert(item) { // insert returns false if the item was already present
            return true;
        }
    }
    false
}

You'll also see $O(n \log n)$ frequently, particularly when sorting. Rust's slice::sort() uses a sophisticated algorithm (Timsort) that falls into this category. It's slower than linear time but significantly faster than quadratic time. When you're deciding between sorting a list first and then scanning it, or just using a HashMap, you're essentially doing a Big-O trade-off analysis.

📋 Practical Task

Optimizing the Duplicate Username Detector

You have been handed a piece of legacy code used to verify if a list of usernames contains any duplicates before they are committed to a database. The current implementation uses a nested loop and is causing timeouts in production as the user base grows.

Your Task: Rewrite the check_for_duplicates function. Replace the $O(n^2)$ nested loop approach with a more efficient $O(n)$ implementation using a HashSet. Ensure the function signature remains the same so that the existing tests still pass.

use std::collections::HashSet;

fn check_for_duplicates(usernames: Vec<String>) -> bool {
    // TODO: Remove the nested loops and implement an O(n) solution
    for i in 0..usernames.len() {
        for j in i + 1..usernames.len() {
            if usernames[i] == usernames[j] {
                return true;
            }
        }
    }
    false
}

fn main() {
    let users = vec![
        "alice".to_string(), 
        "bob".to_string(), 
        "charlie".to_string(), 
        "alice".to_string()
    ];
    
    if check_for_duplicates(users) {
        println!("Duplicates found!");
    } else {
        println!("All usernames are unique.");
    }
}