Big O Notation — Explained with Examples

Big O notation describes algorithm efficiency by expressing how runtime or memory usage grows relative to input size, independent of hardware.

Big O notation classifies algorithms by how their execution time (time complexity) or memory usage (space complexity) scales as input size increases. Common classes include O(1) (constant), O(log n) (logarithmic), O(n) (linear), O(n log n) (linearithmic), O(n²) (quadratic), and O(2ⁿ) (exponential). Big O describes the worst-case upper bound, while Big Θ (theta) describes the average-case tight bound.

Think of Big O like rating a restaurant’s speed based on the number of customers. A coffee shop (O(1)) serves you instantly regardless of how many people are in line. A cafeteria (O(n)) takes longer as the line grows. A slow-cooking restaurant (O(n²)) takes dramatically longer with each additional customer.

Big O helps compare algorithms independently of hardware, programming language, or input specifics. An O(n log n) sort like merge sort will beat an O(n²) sort like bubble sort for large inputs, regardless of how fast the machine is.

// O(1) — constant time: array lookup
function getFirst(arr) {
  return arr[0];
}

// O(n) — linear time: linear search
function find(arr, target) {
  for (let item of arr) {
    if (item === target) return true;
  }
  return false;
}

// O(n²) — quadratic time: bubble sort
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
}

When analyzing algorithms, drop constants and lower-order terms. O(2n + 1000) simplifies to O(n). Focus on the dominant factor that determines growth rate.

Algorithm, Sorting, Hash Table, Binary Search Tree

Sorting Algorithm Complexity