← Back to Library • Computer Science • Intermediate • 8 min read

What Is Big O Notation? Algorithmic Complexity Made Simple

Big O notation is a mathematical notation used in computer science to describe the upper bound of an algorithm's running time or memory usage as the input size (N) grows towards infinity.

💡 Plain-English Analogy

Imagine looking for a name in a phone book. If you check every page one by one from front to back, looking through 100 pages takes 100 seconds, and 1,000 pages takes 1,000 seconds (this is O(N)). But if you open to the middle, see if the name is before or after, and cut the book in half repeatedly, 1,000 pages takes only 10 flips (this is O(log N)). Big O measures how much slower code gets as data grows.

⚙️ Architecture & Under the Hood

Big O characterizes the asymptotic growth rate of functions by dropping lower-order terms and constant coefficients. For instance, f(N) = 3N² + 50N + 2000 simplifies strictly to O(N²). Space complexity measures memory allocations auxiliary to the input.

The Big O Complexity Scale (Fastest to Slowest)

Algorithms are ranked by how their operation count scales relative to input size N.

O(1)       ── Constant Time     (Instant lookup in Hash Map)
O(log N)   ── Logarithmic Time  (Binary search in sorted array)
O(N)       ── Linear Time       (Single pass through an array)
O(N log N) ── Linearithmic Time (Fast sorts: MergeSort, QuickSort)
O(N²)      ── Quadratic Time    (Nested loops, BubbleSort) ⚠️ Sluggish for large N
O(2^N)     ── Exponential Time  (Recursive Fibonacci, brute force) 🛑 Catastrophic

// O(1) Constant Time: Instant regardless of array size
function getFirstElement(arr) {
  return arr[0];
}

// O(N) Linear Time: Execution time scales directly with N
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// O(N^2) Quadratic Time: Nested loops scanning N x N
function hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

Frequently Asked Questions

What is the difference between Big O and Big Omega?

Big O describes the worst-case (upper bound) scenario. Big Omega (Ω) describes the best-case (lower bound) scenario. Big Theta (Θ) describes tight bounds where best and worst cases match.