Eventually Bitwise

Big O Notation

Overview

Big O notation is a mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it is used to classify algorithms according to how their run time or space requirements grow as the input size ($n$) grows.

Core Concepts

  • Time Complexity: How the execution time of an algorithm increases with the size of the input.
  • Space Complexity: How much extra memory an algorithm requires as the input size increases.
  • Common Notations:
    • $O(1)$ – Constant: Execution time is independent of input size (e.g., accessing an array index).
    • $O(\log n)$ – Logarithmic: Execution time grows slowly (e.g., Binary Search).
    • $O(n)$ – Linear: Execution time grows proportionally to input size (e.g., Linear Search).
    • $O(n \log n)$ – Linearithmic: Typical of efficient sorting algorithms (e.g., MergeSort).
    • $O(n^2)$ – Quadratic: Execution time grows quadratically (e.g., Bubble Sort).
    • $O(2^n)$ – Exponential: Execution time doubles with each addition to the input (e.g., recursive Fibonacci).
  • Cases:
    • Worst Case (Big O): The maximum time an algorithm could possibly take.
    • Average Case ($\Theta$): The expected time over all possible inputs.
    • Best Case ($\Omega$): The minimum time an algorithm could take.

Code Examples

// O(1) - Constant
function getFirst(arr: any[]) { return arr[0]; }

// O(n) - Linear
function printAll(arr: any[]) {
    arr.forEach(item => console.log(item));
}

// O(n^2) - Quadratic
function printPairs(arr: any[]) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j]);
        }
    }
}

Use Cases

  • Algorithm Comparison: Deciding between two different approaches to solve the same problem based on performance.
  • Scalability Planning: Estimating if a system will crash or slow down significantly when user growth increases.

Gotchas

  • Ignoring Constants: Big O ignores constant factors (e.g., $O(2n)$ becomes $O(n)$). While helpful for growth trends, constants matter in real-world low-latency systems.
  • Worst Case Focus: Developers often only look at the worst case, but for some algorithms, the average case is far more common.

Related Notes

, ,