Big O Notation

Introduction

In this lesson, we'll explore Big O Notation, a key tool for analyzing algorithm efficiency. Understanding Big O helps us identify performance bottlenecks and choose the right algorithm for specific contexts.

What is Big O Notation?

Big O Notation is a mathematical way to describe an algorithm's time and space complexity, giving us a high-level view of how its performance scales with input size.

Key Points

Time Complexity: How the runtime changes with input size.
Space Complexity: How memory usage changes with input size.
Asymptotic Analysis: Behavior of an algorithm as input size approaches infinity.

Common Big O Notations

Let's look at some common Big O Notations and what they mean in terms of algorithm efficiency.

O(1) - Constant Time

An algorithm with O(1) complexity runs in constant time, regardless of the input size.

Think of Constant Time like looking up a specific page in a phone book by going straight to that page. It doesn't matter how thick the phone book is; finding the page takes the same amount of time because you go directly to it without needing to check the other pages.

Imagine looking up a specific page in a phone book by going directly to it—no matter how thick the book is, it takes the same time because you skip straight to the page.

fn main() {
    let numbers = vec![10, 20, 30, 40, 50];

    let first = get_first_element(&numbers);

    println!("The first element is: {}", first);
}

fn get_first_element(vec: &Vec<i32>) -> i32 {
    vec[0] // Accessing the first element is a constant-time operation
}

The main function creates a vector numbers and calls get_first_element to retrieve the first element. The time to get the first element is constant, no matter how many elements are in the vector.

The get_first_element function accesses the first element directly, which is a constant-time operation since it directly accesses the memory location.

O(n) - Linear Time

An algorithm with O(n) complexity runs in linear time, meaning the runtime grows linearly with the input size.

Linear Time means the runtime increases proportionally with the input size. If the input size doubles, the time taken roughly doubles.

Imagine searching for a book in a single line of books—you have to check each one. The time to find your book increases directly with the number of books.

fn main() {
    let numbers = vec![10, 20, 30, 40, 50];
    let target = 30;

    let found = find_element(&numbers, target);

    println!("Element found: {}", found);
}

fn find_element(vec: &Vec<i32>, target: i32) -> bool {
    for &item in vec.iter() {
        if item == target {
            return true; // Found the target
        }
    }
    false // Target not found
}

The main function creates a vector numbers and calls find_element to check if a number is present. The time taken depends on the number of elements in the vector.

The find_element function iterates through each element to find the target. The time increases linearly with the vector's size.

O(n^2) - Quadratic Time

An algorithm with O(n^2) complexity runs in quadratic time, meaning the runtime grows quadratically with the input size.

Quadratic Time means that if the input size doubles, the runtime will roughly quadruple. This occurs because the algorithm involves nested loops, each iterating over the input size.

Imagine comparing each pair of students in a class to find those with the same birthday. If there are n students, you would need to perform n * (n - 1) / 2 comparisons (approximately n^2 comparisons) to check every pair. As the number of students increases, the number of comparisons grows significantly.

fn main() {
    let mut numbers = vec![64, 25, 12, 22, 11];

    bubble_sort(&mut numbers);

    println!("Sorted array: {:?}", numbers);
}

fn bubble_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
    for i in 0..n {
        for j in 0..n - 1 - i {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

The main function creates a vector numbers and sorts it using the bubble_sort function. The sorting operation has a time complexity of O(n^2).

The bubble_sort function takes a mutable reference to a vector arr and sorts it using the bubble sort algorithm. The time complexity is quadratic because the outer loop iterates over each element, while the inner loop compares and swaps adjacent elements, resulting in roughly n * (n - 1) / 2 comparisons and swaps.

O(log n) - Logarithmic Time

An algorithm with O(log n) complexity runs in logarithmic time, meaning the runtime grows logarithmically with the input size. This is common in algorithms that divide the problem in half with each step, such as binary search.

Logarithmic Time means that as the input size doubles, the runtime increases by a constant amount rather than doubling. This is because the algorithm significantly reduces the problem size with each step.

Imagine you're searching for a name in a phone book organized alphabetically. If you start in the middle and determine whether the name you're looking for is before or after that point, you effectively cut the search space in half with each step, making the search much faster than checking each name one by one.

fn main() {
    let numbers = vec![10, 20, 30, 40, 50];
    let target = 30;

    match binary_search(&numbers, target) {
        Some(index) => println!("Element found at index: {}", index),
        None => println!("Element not found"),
    }
}

fn binary_search(arr: &Vec<i32>, target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len() as isize - 1;

    while left <= right {
        let mid = (left + right) / 2;
        let mid_value = arr[mid as usize];

        if mid_value == target {
            return Some(mid as usize);
        } else if mid_value < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    None // Target not found
}

The main function creates a sorted vector numbers and uses binary_search to find the target. The search operation has a time complexity of O(log n).

The binary_search function performs a binary search on a sorted vector arr to find the target value. The time complexity is logarithmic because the search space is halved with each step. It starts with the entire array (from left to right). In each iteration, it calculates the midpoint and compares the target with the midpoint value. If the target is less than the midpoint, the search continues in the left half; if it's greater, the search continues in the right half.

O(n log n) - Linearithmic Time

An algorithm with O(n log n) complexity runs in linearithmic time, which is typical of efficient sorting algorithms like Merge Sort and Quick Sort.

Linearithmic Time means that the algorithm's runtime increases faster than Linear Time but slower than Quadratic Time. It grows proportionally to the size of the input multiplied by the logarithm of the size of the input.

Imagine you have a large stack of unsorted papers that you want to sort. You divide the stack into smaller stacks, sort each smaller stack individually, and then combine them back together in order. The process of dividing, sorting, and merging each stack grows in a way that reflects Linearithmic Time complexity.

fn main() {
    let mut numbers = vec![38, 27, 43, 3, 9, 82, 10];

    merge_sort(&mut numbers);
    println!("Sorted array: {:?}", numbers);
}

fn merge_sort(arr: &mut Vec<i32>) {
    let len = arr.len();
    if len <= 1 {
        return;
    }

    let mid = len / 2;
    let mut left = arr[..mid].to_vec();
    let mut right = arr[mid..].to_vec();

    merge_sort(&mut left);
    merge_sort(&mut right);

    merge(arr, &left, &right);
}

fn merge(arr: &mut Vec<i32>, left: &Vec<i32>, right: &Vec<i32>) {
    let mut left_idx = 0;
    let mut right_idx = 0;
    let mut arr_idx = 0;

    while left_idx < left.len() && right_idx < right.len() {
        if left[left_idx] <= right[right_idx] {
            arr[arr_idx] = left[left_idx];
            left_idx += 1;
        } else {
            arr[arr_idx] = right[right_idx];
            right_idx += 1;
        }
        arr_idx += 1;
    }

    while left_idx < left.len() {
        arr[arr_idx] = left[left_idx];
        left_idx += 1;
        arr_idx += 1;
    }

    while right_idx < right.len() {
        arr[arr_idx] = right[right_idx];
        right_idx += 1;
        arr_idx += 1;
    }
}

In the main function: We create a vector numbers and sort it using merge_sort. The sorting operation's time complexity is O(n log n).

Function merge_sort: This function performs the Merge Sort algorithm. It recursively divides the vector into two halves until each half is trivially sorted (i.e., has one or zero elements). It then merges the sorted halves using the merge function. The time complexity of the merge_sort function is O(n log n).

Function merge: This function merges two sorted arrays left and right into a single sorted array arr. The time complexity of the merge function is O(n).

Why is Big O Notation Important?

Understanding Big O Notation helps you:

Evaluate and compare the efficiency of different algorithms.
Identify performance bottlenecks in your code.
Make informed decisions about which algorithm to use based on the context and constraints.

Conclusion

In this lesson, we've introduced Big O Notation and discussed its importance in analyzing algorithm efficiency. We also covered some common Big O Notations with Rust code examples. In the next lesson, we will dive into arrays and vectors, exploring their properties and usage in Rust.

Thank you for joining me on this journey to learn Rust and computer science concepts. Stay tuned for the next lesson!

Learn Data Structures and Algorithms