Step 1 of 7

Big-O: counting the work

At work, correct isn't enough: code has to be fast enough for the real amount of data. A function that's instant on your 10-row test file can take hours on the production table with 10 million rows. Time complexity describes how the work a piece of code does grows as the input size n grows. We write it in Big-O notation, which keeps only the part that dominates for large n and ignores constant factors.

The difference is enormous once n is big:

fn main() {
    println!("{:>7} {:>8} {:>10} {:>12}", "n", "log2 n", "n log2 n", "n * n");
    for n in [10u64, 100, 1_000, 100_000] {
        let log = n.ilog2() as u64; // integer base-2 logarithm
        println!("{n:>7} {log:>8} {:>10} {:>12}", n * log, n * n);
    }
}

      n   log2 n   n log2 n        n * n
     10        3         30          100
    100        6        600        10000
   1000        9       9000      1000000
 100000       16    1600000  10000000000

A useful rule of thumb: a debug build (like the one this site uses) does roughly 100 million simple steps per second; a release build is often 10 to 50 times faster. The time limit here is 2 seconds. So for n = 100,000, an O(n log n) solution takes a couple of million steps (instant) while an O(n²) one takes ten billion (minutes). Many exercises in this phase include a big test for exactly that reason.

Counting the work in real code

Here are two ways to check a list of ids for duplicates:

fn has_duplicate_slow(ids: &[u64]) -> bool {
    // compares every pair: n * (n - 1) / 2 comparisons, O(n²)
    for i in 0..ids.len() {
        for j in i + 1..ids.len() {
            if ids[i] == ids[j] {
                return true;
            }
        }
    }
    false
}

fn has_duplicate_sorted(ids: &[u64]) -> bool {
    // sort a copy, O(n log n); then equal ids sit next to each other, O(n)
    let mut sorted = ids.to_vec();
    sorted.sort_unstable();
    sorted.windows(2).any(|pair| pair[0] == pair[1])
}

fn main() {
    let ids = [42, 7, 19, 7, 3];
    println!("{} {}", has_duplicate_slow(&ids), has_duplicate_sorted(&ids));
}

true true

The second one does O(n log n) + O(n) work, and Big-O keeps only the biggest term: O(n log n). Constants are dropped too: two passes over the data are O(2n), which is just O(n).

A few more words you'll hear:

• Worst case vs average case: a HashMap lookup is O(1) on average, but O(n) in a pathological worst case. Big-O usually means the worst case unless someone says otherwise.
• Amortized: Vec::push is O(1) amortized. Now and then the Vec is full and copies everything into a block twice as big (O(n)), but that happens so rarely that the average per push stays constant.
• Space complexity: extra memory used. has_duplicate_sorted needs O(n) extra memory for the copy; has_duplicate_slow needs O(1).

Common mistakes

• Hidden loops. v.contains(&x), v.iter().position(...), s.chars().nth(i), v.remove(0) and v.insert(0, x) are all O(n). Inside a loop over v, they make the whole thing O(n²).
• "O(1) means fast." It means "doesn't grow with n". A HashMap lookup hashes the key every time; for five items a plain Vec scan is often quicker.
• Testing only with tiny inputs. Everything is fast with 10 items. Test with the size you'll really get.

Your task

Write fn has_duplicate(ids: &[u64]) -> bool in O(n) on average, using a HashSet. Remember that HashSet::insert returns false when the value was already there. The tests include 100,000 ids.

Challenge 2

The log analyzer wants the first word that repeats: the word whose second appearance comes earliest. In ["ok", "error", "warn", "error", "ok"] that's "error" (it repeats at position 3, before "ok" repeats at position 4).

Write fn first_repeat<'a>(words: &[&'a str]) -> Option<&'a str> in O(n) with a HashSet. (The 'a says the returned word lives as long as the words in the slice; the lifetimes module explained why the compiler needs it here.) The tests include 100,000 words.

Challenge 3

A gift shop shows two items whose prices add up exactly to the customer's budget. Write fn two_sum(prices: &[i64], budget: i64) -> Option<(usize, usize)> that returns the indices (i, j) with i < j of two different items whose prices sum to budget.

If several pairs work, return the one that is completed first: the smallest j, and for that j the smallest i. Return None if no pair works.

Checking every pair is O(n²), and the tests have 100,000 prices. Instead, walk the list once and keep a HashMap from price to the index where you first saw it: for each price p at index j, look up budget - p.

Next: Linear and binary search