Activity 31: Big O Complexity Analysis

Instructions

For each problem below:

1. Determine the time complexity (Big O notation)
2. Determine the space complexity (Big O notation)
3. Justify your answer briefly (1-2 sentences)
4. Answer the follow-up question about optimization or efficiency

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: ________________

Can this be made more efficient? Or is this optimal?

________________________________

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: ________________

Can this be made more efficient? Or is this optimal?

________________________________

Problem 3: Checking Sorted Array

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

Time complexity: ________________

Space complexity: ________________

Can this be made more efficient? Or is this optimal?

________________________________

Problem 4: Tricky Loop

#![allow(unused)]
fn main() {
fn mystery(n: usize) -> usize {
    let mut count = 0;
    let mut i = 1;
    while i < n {
        count += 1;
        i *= 2;  // note * not +
    }
    count
}
}

Time complexity: ________________

Space complexity: ________________

Can this be made more efficient? Or is this optimal?

________________________________

Problem 5: Multiple Passes

#![allow(unused)]
fn main() {
fn count_above_average(arr: &[i32]) -> usize {
    // First pass: calculate average
    let mut sum = 0;
    for &num in arr {
        sum += num;
    }
    let avg = sum / arr.len() as i32;

    // Second pass: count above average
    let mut count = 0;
    for &num in arr {
        if num > avg {
            count += 1;
        }
    }
    count
}
}

Time complexity: ________________

Space complexity: ________________

Can this be made more efficient? Or is this optimal?

________________________________

Problem 6: HashMap Lookup

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn count_frequencies(arr: &[i32]) -> HashMap<i32, usize> {
    let mut freq = HashMap::new();
    for &num in arr {
        *freq.entry(num).or_insert(0) += 1;
    }
    freq
}
}

Time complexity: ________________

Space complexity: ________________

Can this be made more efficient? Or is this optimal?

________________________________

Problem 7: Matrix Operations

#![allow(unused)]
fn main() {
fn matrix_multiply(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = a.len();
    let m = b[0].len();
    let p = a[0].len();

    let mut result = vec![vec![0; m]; n];

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

Time complexity: ________________

Space complexity: ________________

Can this be made more efficient? Or is this optimal?

________________________________

Bonus Challenge: Space-Time Tradeoff

Consider these two approaches to check if an array has duplicates:

Version A:

#![allow(unused)]
fn main() {
fn has_duplicates_v1(arr: &[i32]) -> 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() {
use std::collections::HashSet;

fn has_duplicates_v2(arr: &[i32]) -> bool {
    let mut seen = HashSet::new();
    for &val in arr {
        if seen.contains(&val) {
            return true;
        }
        seen.insert(val);
    }
    false
}
}

Version A:

• Time: _______ Space: _______

Version B:

• Time: _______ Space: _______

1. When might you prefer Version A?

2. When might you prefer Version B?