Algorithm Complexity Guide
Tutorial Video
Text description (accessibility)
This video demonstrates the "Algorithm Complexity Guide" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Understanding time and space complexity is essential for writing software that scales. Key difference from OCaml: | Aspect | Rust | OCaml |
Tutorial
The Problem
Understanding time and space complexity is essential for writing software that scales. A function that runs in 1ms for n=100 might take 10 seconds for n=10,000 if it's O(n^2) ā and 3 years for n=1,000,000. Engineers need an intuitive grasp of which complexity class their code falls into, and which operations trigger which class. This reference guide concretizes the abstract Big-O notation with real Rust examples: constant-time array access, logarithmic binary search, linear scans, O(n log n) sorting, quadratic nested loops, exponential backtracking. Each example demonstrates not just the code but why it achieves its complexity class.
🎯 Learning Outcomes
Code Example
#![allow(clippy::all)]
//! # Algorithm Complexity Guide
//!
//! Reference for common algorithm complexities.
/// O(1) - Constant time
pub fn constant_time_example(arr: &[i32]) -> Option<i32> {
arr.first().copied()
}
/// O(log n) - Logarithmic time
pub fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
arr.binary_search(&target).ok()
}
/// O(n) - Linear time
pub fn linear_search(arr: &[i32], target: i32) -> Option<usize> {
arr.iter().position(|&x| x == target)
}
/// O(n log n) - Linearithmic time
pub fn merge_sort(mut arr: Vec<i32>) -> Vec<i32> {
if arr.len() <= 1 {
return arr;
}
let mid = arr.len() / 2;
let right = merge_sort(arr.split_off(mid));
let left = merge_sort(arr);
merge(left, right)
}
fn merge(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let mut result = Vec::with_capacity(a.len() + b.len());
let (mut i, mut j) = (0, 0);
while i < a.len() && j < b.len() {
if a[i] <= b[j] {
result.push(a[i]);
i += 1;
} else {
result.push(b[j]);
j += 1;
}
}
result.extend_from_slice(&a[i..]);
result.extend_from_slice(&b[j..]);
result
}
/// O(nĀ²) - Quadratic time
pub fn bubble_sort(arr: &mut [i32]) {
let n = arr.len();
for i in 0..n {
for j in 0..n - i - 1 {
if arr[j] > arr[j + 1] {
arr.swap(j, j + 1);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_constant() {
assert_eq!(constant_time_example(&[1, 2, 3]), Some(1));
}
#[test]
fn test_binary() {
assert_eq!(binary_search(&[1, 2, 3, 4, 5], 3), Some(2));
}
#[test]
fn test_linear() {
assert_eq!(linear_search(&[1, 2, 3, 4, 5], 3), Some(2));
}
#[test]
fn test_merge() {
assert_eq!(merge_sort(vec![3, 1, 4, 1, 5, 9]), vec![1, 1, 3, 4, 5, 9]);
}
}Key Differences
| Aspect | Rust | OCaml |
|---|---|---|
len() | Vec::len() is O(1) | List.length is O(n), Array.length is O(1) |
| Indexing | slice[i] is O(1) | array.(i) is O(1), List.nth is O(n) |
| Sort | slice.sort() is O(n log n) | List.sort is O(n log n) |
| HashMap | O(1) amortized insert/lookup | Hashtbl O(1) average |
| BTreeMap | O(log n) insert/lookup | Map.t O(log n) |
| Stack overflow | Happens at ~8KB stack depth | TCO prevents for tail calls |
OCaml Approach
OCaml's complexity guide mirrors Rust's: List.hd for O(1), List.nth for O(n) (lists are not random-access!), array .(i) for O(1), Array.binary_search for O(log n). OCaml's lazy Seq enables O(1) per-element consumption of infinite sequences. List.length is O(n) in OCaml (not cached), unlike Rust's Vec::len() which is O(1). This highlights a critical difference: OCaml lists don't cache length; Array.length is O(1). Understanding the OCaml stdlib's complexity is essential for writing efficient OCaml.
Full Source
#![allow(clippy::all)]
//! # Algorithm Complexity Guide
//!
//! Reference for common algorithm complexities.
/// O(1) - Constant time
pub fn constant_time_example(arr: &[i32]) -> Option<i32> {
arr.first().copied()
}
/// O(log n) - Logarithmic time
pub fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
arr.binary_search(&target).ok()
}
/// O(n) - Linear time
pub fn linear_search(arr: &[i32], target: i32) -> Option<usize> {
arr.iter().position(|&x| x == target)
}
/// O(n log n) - Linearithmic time
pub fn merge_sort(mut arr: Vec<i32>) -> Vec<i32> {
if arr.len() <= 1 {
return arr;
}
let mid = arr.len() / 2;
let right = merge_sort(arr.split_off(mid));
let left = merge_sort(arr);
merge(left, right)
}
fn merge(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let mut result = Vec::with_capacity(a.len() + b.len());
let (mut i, mut j) = (0, 0);
while i < a.len() && j < b.len() {
if a[i] <= b[j] {
result.push(a[i]);
i += 1;
} else {
result.push(b[j]);
j += 1;
}
}
result.extend_from_slice(&a[i..]);
result.extend_from_slice(&b[j..]);
result
}
/// O(nĀ²) - Quadratic time
pub fn bubble_sort(arr: &mut [i32]) {
let n = arr.len();
for i in 0..n {
for j in 0..n - i - 1 {
if arr[j] > arr[j + 1] {
arr.swap(j, j + 1);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_constant() {
assert_eq!(constant_time_example(&[1, 2, 3]), Some(1));
}
#[test]
fn test_binary() {
assert_eq!(binary_search(&[1, 2, 3, 4, 5], 3), Some(2));
}
#[test]
fn test_linear() {
assert_eq!(linear_search(&[1, 2, 3, 4, 5], 3), Some(2));
}
#[test]
fn test_merge() {
assert_eq!(merge_sort(vec![3, 1, 4, 1, 5, 9]), vec![1, 1, 3, 4, 5, 9]);
}
}#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_constant() {
assert_eq!(constant_time_example(&[1, 2, 3]), Some(1));
}
#[test]
fn test_binary() {
assert_eq!(binary_search(&[1, 2, 3, 4, 5], 3), Some(2));
}
#[test]
fn test_linear() {
assert_eq!(linear_search(&[1, 2, 3, 4, 5], 3), Some(2));
}
#[test]
fn test_merge() {
assert_eq!(merge_sort(vec![3, 1, 4, 1, 5, 9]), vec![1, 1, 3, 4, 5, 9]);
}
}Deep Comparison
OCaml vs Rust: Algorithm Complexity Guide
Overview
See the example.rs and example.ml files for detailed implementations.
Key Differences
| Aspect | OCaml | Rust |
|---|---|---|
| Type system | Hindley-Milner | Ownership + traits |
| Memory | GC | Zero-cost abstractions |
| Mutability | Explicit ref | mut keyword |
| Error handling | Option/Result | Result<T, E> |
See README.md for detailed comparison.
Exercises
Vec::push: prove that n pushes cost O(n) total despite occasional O(n) copies.HashMap::get is O(1) amortized but has O(n) worst case, and when worst case can be triggered.