Big-O Notation Explained: Measuring Algorithm Efficiency

Big-O notation describes how an algorithm’s running time (or memory use) grows as the input size grows. It throws away constants and small details to capture the one thing that matters at scale: the shape of the growth. When someone says an algorithm is “O(n)”, they mean its work grows roughly in proportion to the input size n.

It’s the universal language for comparing algorithms — and the single most common topic in technical interviews.

Why we ignore constants

Big-O cares about growth, not exact counts. An algorithm that does 2n + 100 steps and one that does n steps are both O(n): as n gets huge, the doubling and the +100 stop mattering compared to how the cost scales. We keep only the dominant term and drop coefficients.

So 3n^2 + 5n + 9 becomes O(n²), because for large n the n² term dwarfs the rest.

O(1) — constant time

The operation takes the same time no matter how big the input is. Reading an array element by index is the classic example:

int first(const std::vector<int>& a) {
    return a[0]; // one step, regardless of size
}

int first(int[] a) {
    return a[0]; // one step, regardless of size
}

function first(a) {
  return a[0]; // one step, regardless of size
}

def first(a):
    return a[0]  # one step, regardless of size

O(n) — linear time

The work grows in direct proportion to the input. Summing every element must touch each one once:

long sum(const std::vector<int>& a) {
    long total = 0;
    for (int x : a) total += x; // n iterations
    return total;
}

long sum(int[] a) {
    long total = 0;
    for (int x : a) total += x; // n iterations
    return total;
}

function sum(a) {
  let total = 0;
  for (const x of a) total += x; // n iterations
  return total;
}

def sum_all(a):
    total = 0
    for x in a:      # n iterations
        total += x
    return total

O(n²) — quadratic time

Nested loops over the same input. Each element is paired with every other — n × n work. This is fine for small inputs but explodes quickly:

bool hasDuplicate(const std::vector<int>& a) {
    for (size_t i = 0; i < a.size(); i++)
        for (size_t j = i + 1; j < a.size(); j++)
            if (a[i] == a[j]) return true;
    return false;
}

boolean hasDuplicate(int[] a) {
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] == a[j]) return true;
    return false;
}

function hasDuplicate(a) {
  for (let i = 0; i < a.length; i++)
    for (let j = i + 1; j < a.length; j++)
      if (a[i] === a[j]) return true;
  return false;
}

def has_duplicate(a):
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] == a[j]:
                return True
    return False

Going deeper: The same hasDuplicate problem drops to O(n) using a hash set. Recognizing when a nested loop can become a single pass with extra memory is a core DSA skill — see problem-solving patterns.

The common growth classes

From fastest-growing (worst) to slowest-growing (best) for large n:

Time vs space complexity

• Time complexity — how the number of operations grows.
• Space complexity — how the extra memory grows (not counting the input itself).

An algorithm can trade one for the other: using a hash table costs O(n) space but can cut time from O(n²) to O(n). Knowing which to optimize is the art of DSA.

Best, average, and worst case

Big-O usually describes the worst case (an upper bound on growth), because that’s the guarantee that matters in interviews and production. Some problems also discuss average case (typical input) and best case (luckiest input).

For beginners: When in doubt, count the loops. One loop over the input → likely O(n). A loop inside a loop → likely O(n²). Halving the problem each step → likely O(log n).

Next: practice spotting complexity with the complexity exercises, or move on to Arrays.