Activity 9: Big O Complexity Analysis

Instructions

For each problem below, write:

1. Time complexity in Big O, for the worst case
2. Space complexity in Big O: the extra memory the function uses, not counting its input
3. Why, in one sentence

Problem 1: Array Sum

#![allow(unused)]
fn main() {
fn sum_array(arr: &[i32]) -> i32 {
    let mut total = 0;
    for &num in arr {
        total += num;
    }
    total
}
}

Time complexity: ________________

Space complexity: ________________

Why: ________________________________

Problem 2: Finding First Duplicate

#![allow(unused)]
fn main() {
fn find_first_duplicate(arr: &[i32]) -> Option<i32> {
    for i in 0..arr.len() {
        for j in (i+1)..arr.len() {
            if arr[i] == arr[j] {
                return Some(arr[i]);
            }
        }
    }
    None
}
}

Time complexity: ________________

Space complexity: ________________

Why: ________________________________

Problem 3: Tricky Loop

#![allow(unused)]
fn main() {
fn mystery(n: usize) -> usize {
    let mut count = 0;
    let mut remaining = n;
    while remaining > 0 {
        remaining /= 10;
        count += 1;
    }
    count
}
}

Time complexity: ________________

Space complexity: ________________

Why: ________________________________

Problem 4: Multiplying Grids

#![allow(unused)]
fn main() {
fn multiply_grids(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = a.len();  // both grids are n by n
    let mut result = vec![vec![0; n]; n];

    for i in 0..n {
        for j in 0..n {
            for k in 0..n {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    result
}
}

Time complexity: ________________

Space complexity: ________________

Why: ________________________________

Bonus: Trading space for time

Both functions answer the same question: does this array have the same number in it twice? Every value in the array is less than 1,000.

Version A:

#![allow(unused)]
fn main() {
fn has_duplicates_a(arr: &[usize]) -> bool {
    for i in 0..arr.len() {
        for j in (i+1)..arr.len() {
            if arr[i] == arr[j] {
                return true;
            }
        }
    }
    false
}
}

Version B:

#![allow(unused)]
fn main() {
fn has_duplicates_b(arr: &[usize]) -> bool {
    let mut seen = [false; 1000];
    for &value in arr {
        if seen[value] {
            return true;
        }
        seen[value] = true;
    }
    false
}
}

Version A:

• Time: _______ Space: _______

Version B:

• Time: _______ Space: _______

1. When might you prefer Version A?

2. When might you prefer Version B?

Solutions

Problem 1: O(n) time, O(1) space. One pass over the array, and only total is kept.

Problem 2: O(n^2) time, O(1) space. Nested loops over the array; worst case is no duplicate at all. Best case is O(1), when the first two numbers match.

Problem 3: O(log n) time, O(1) space. It counts the digits in n: each pass divides by 10, the bunnies in reverse. mystery(1,000) is 4 and mystery(1,000,000) is 7.

Problem 4: O(n^3) time, O(n^2) space. Three nested loops of n; the result is a new n by n grid.

Bonus, Version A: O(n^2) time, O(1) space.

Bonus, Version B: O(n) time. Space is always 1,000 true/false values no matter how long the array is: O(1) as the array grows, but it grows with the largest value allowed, the same as the sieve's O(limit).

• Prefer A when values could be huge (an array covering every possible value would be enormous), memory is tight, or the arrays are tiny
• Prefer B when arrays are long, values are small, and speed matters