What Is Big O Notation? A Beginner's Guide

If you've spent any time browsing coding interview prep or algorithm discussions, you've run into Big O notation. It looks like math notation because it is, but the idea behind it is refreshingly practical: it's just a way to describe how slow or fast your code gets as the input grows.

The Core Idea

Big O notation describes how the number of operations an algorithm performs scales with the size of its input, usually called n. It doesn't care about your exact hardware or programming language. It cares about the shape of the growth curve as n gets large.

It also typically describes the worst-case scenario, so you know the upper bound on how bad things can get, rather than an average or best case that might be misleading.

The Common Big O Classes

O(1) — Constant time. The operation takes the same amount of time no matter how big the input is. Accessing an array element by index is a classic example: arr[5] takes the same time whether the array has 10 elements or 10 million.

O(log n) — Logarithmic time. The work needed grows slowly as the input grows, because the algorithm cuts the problem in half each step. Binary search is the textbook example: searching a sorted array of a million items takes at most about 20 comparisons.

O(n) — Linear time. The work grows directly in proportion to the input. Looping through an array once to find the maximum value is O(n), since doubling the array roughly doubles the work.

O(n log n) — Linearithmic time. Common in efficient sorting algorithms like merge sort and quicksort. It's slower than linear but much faster than quadratic for large inputs.

O(n²) — Quadratic time. Common with nested loops over the same data, like comparing every item to every other item. Bubble sort is a classic O(n²) example. This gets slow fast: doubling the input quadruples the work.

O(2ⁿ) — Exponential time. Work doubles with every additional input element. Naive recursive solutions to problems like the Fibonacci sequence often fall here, and they become impractical very quickly as n grows.

A Concrete Comparison

Here are two ways to check whether an array contains any duplicate values:

// O(n²) — nested loop compares every pair
bool hasDuplicateSlow(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (arr[i] == arr[j]) return true;
    }
  }
  return false;
}

The nested-loop version compares every element to every other element, giving O(n²) behavior. A version using a hash set instead can check for duplicates in a single pass, giving O(n) behavior. For small arrays, both feel instant. For an array of a million items, the difference is the gap between a program that finishes immediately and one that noticeably hangs.

Why This Matters in Practice

Most code you write won't run into performance problems at small scale, and premature optimization is a real trap beginners fall into. But understanding Big O helps you spot the code that will become a problem once real users and real data show up, and it's a near-universal topic in technical interviews.

Where to Go From Here

Big O becomes intuitive once you start timing your own code against different input sizes and noticing the patterns. Try writing both an O(n) and an O(n²) solution to the same small problem and compare how they behave as you scale the input up.

If you want to build a strong foundation in algorithms and problem-solving with guided lessons and a live code playground, CodeFacility's advanced courses cover complexity, data structures, and efficient code step by step and completely free.