Big O Notation Explained With Practical Examples

Big O notation describes how the work an algorithm does grows as its input grows. It ignores machine speed, language, and constant factors, and keeps only the dominant growth rate, so you can compare approaches before writing a line of production code. This article gives you big O notation explained through code you already write every day, plus the rules that let you derive complexity quickly and defend it in an interview.

What is Big O notation, really?

Formally, saying a function f(n) is O(g(n)) means there is some constant c and some input size n0 beyond which f(n) never exceeds c times g(n). In plain terms: Big O is an upper bound on growth. It answers the question "if I double the input, roughly how much more work happens?"

That framing matters because Big O is not a stopwatch. An O(n) loop in Python can be slower than an O(n log n) sort in C for small inputs. What Big O guarantees is the shape of the curve. Once n is large enough, the shape always wins.

For a deeper, structured walkthrough of the definitions, see the Big O notation guide and the companion guide on time and space complexity.

Big O vs Big Theta vs Big Omega

• Big O (O) is an upper bound: growth is at most this fast.
• Big Omega (Ω) is a lower bound: growth is at least this fast.
• Big Theta (Θ) is a tight bound: growth is exactly this fast, up to constants.

In industry and in interviews, people usually say "Big O" when they mean the tight bound for the worst case. That is fine as long as you are precise when it matters, for example when an algorithm's best and worst cases differ.

The common complexity classes with examples

The table below lists the classes you will meet most often, ordered from fastest-growing-slowest to fastest-growing-fastest.

O(1): constant time

Constant time means the work does not depend on n. Reading arr[i], pushing onto a stack, or checking a hash set are all O(1). "Constant" does not mean "fast"; it means "does not grow". A function that always does 10,000 operations is still O(1).

O(log n): logarithmic time

Logarithmic algorithms throw away a fixed fraction of the remaining input on every step. Binary search halves the range each iteration, so a sorted array of about a million items needs only around 20 comparisons. If you want to see why the halving rule is safe, read binary search is a decision rule, not a trick.

O(n) and O(n log n)

Linear time touches each element a constant number of times. O(n log n) is the natural cost of comparison-based sorting: you split the input log n times and do linear work at each level. When a problem feels like it needs sorting first, the sort usually sets the floor for the whole solution.

O(n²) and worse

Quadratic time usually comes from comparing every element with every other element. It is fine for a few hundred items and painful for a few hundred thousand. Exponential and factorial time appear when you enumerate every subset or ordering; these are only viable for very small n, or when you can prune aggressively.

How to calculate Big O from code

You rarely need the formal definition. Apply these rules in order:

1. Count the loops that depend on n. A loop over n items is O(n). A loop nested inside it is multiplied: O(n × n).
2. Add sequential steps, then keep the largest. O(n) followed by O(n²) is O(n + n²), which simplifies to O(n²).
3. Drop constants. O(3n) is O(n). O(n/2) is O(n).
4. Use different variables for different inputs. Looping over array a then array b is O(a + b), not O(n). Nesting them is O(a × b).
5. For recursion, multiply branches by depth. A function that calls itself twice with n − 1 builds a tree of about 2^n calls.
6. Remember hidden costs. String concatenation in a loop, list.contains, array.slice, and indexOf are all linear operations that can quietly turn O(n) into O(n²).

A worked example: finding duplicates

Here are two ways to check whether an array contains a duplicate. The first compares every pair. The second trades memory for speed with a hash set.

// O(n²) time, O(1) extra space
function hasDuplicateBrute(nums: number[]): boolean {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) return true;
    }
  }
  return false;
}

// O(n) time on average, O(n) extra space
function hasDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

// O(n log n) time, O(1) extra space if sorting in place is allowed
function hasDuplicateSorted(nums: number[]): boolean {
  nums.sort((a, b) => a - b);
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) return true;
  }
  return false;
}

The inner loop of the brute-force version runs n − 1, then n − 2, and so on, which sums to about n²/2 comparisons. Dropping the constant gives O(n²). The hash set version does one O(1) average lookup per element, so it is O(n). The sorted version is dominated by the sort. None of these is universally "best": the right choice depends on whether memory or mutation is acceptable.

Space complexity is Big O too

Big O applies to memory as well as time. Space complexity counts the extra memory an algorithm allocates as n grows, not the input itself. The hash set above uses O(n) extra space. A recursive function uses stack space proportional to its maximum depth, so a recursive DFS on a linked-list-shaped tree is O(n) space even if it allocates nothing on the heap.

When you state a complexity, give both: "O(n) time and O(n) space" is a complete answer. "O(n)" alone invites a follow-up question.

Best, average, and worst case

One algorithm can have several complexities depending on the input:

• Quicksort is O(n log n) on average but O(n²) in the worst case when pivots are chosen badly.
• Hash map lookups are O(1) on average but can degrade to O(n) when many keys collide.
• Insertion sort is O(n) on already-sorted input and O(n²) in general.

Worst case is the default in interviews because it is a guarantee. Mention the average case when it is what actually matters in practice, and say why.

Amortized complexity

Some operations are occasionally expensive but cheap on average across a sequence. Appending to a dynamic array is the classic example: most appends are O(1), and once in a while the array doubles its capacity and copies everything. Spread across all appends, the cost per append is still O(1). That is amortized O(1), which is different from average case because it holds for every sequence of operations, not just typical inputs.

Common Big O mistakes

• Calling two independent inputs "n" and hiding a real O(a × b) cost.
• Forgetting the cost of built-ins like sorting, slicing, or substring creation.
• Ignoring recursion stack space.
• Treating O(1) as "instant" when the constant is huge.
• Over-optimizing a path that only ever sees tiny inputs.

Explaining complexity clearly is its own skill. The guide on complexity communication shows how to present your analysis concisely under interview pressure.

Key takeaways

• Big O describes how work grows with input size, not how many milliseconds something takes.
• Nested loops multiply, sequential steps add, and you keep only the dominant term.
• Drop constants, but keep separate variables for separate inputs.
• Always state both time and space complexity, including recursion stack depth.
• Distinguish worst case, average case, and amortized cost when they differ.

Frequently asked questions

What does O(n) mean in simple terms?

O(n) means the work grows in direct proportion to the input size. If you double the number of items, the algorithm does roughly twice as much work. A single loop over an array is the most common example.

Is O(log n) faster than O(n)?

For large inputs, yes. O(log n) grows extremely slowly because each step discards a fraction of the remaining input. For very small inputs, constant factors can make an O(n) approach faster in practice, but the logarithmic one always wins as n grows.

Why do we drop constants in Big O?

Constants depend on hardware, language, and implementation details, while Big O is meant to capture the growth rate that remains once inputs get large. O(2n) and O(n) both double when n doubles, so they belong to the same class. Constants still matter when comparing two algorithms of the same class.

What is the Big O of a hash map lookup?

A hash map lookup is O(1) on average, assuming a good hash function and a reasonable load factor. In the worst case, when many keys collide, it can degrade to O(n), although many modern implementations mitigate that with tree-based buckets.