Big O Notation is a way to measure how efficiently your code performs as the input size grows.

Code that works perfectly on small inputs can slow down, crash, or time out when the input becomes large.

Understanding Big O helps you avoid slow, inefficient solutions and write code that scales.

It’s also one of the most important topics in coding interviews.

You’ll almost always be asked to explain the time and space complexity of your solution. The more efficient your approach, the stronger your chances of passing.

In this chapter, I’ll break down:

Let's get started.

What exactly is Big O Notation?

Big O is a mathematical way to describe how the performance of an algorithm changes as the size of the input grows.

It doesn’t tell you the exact time your code will take.

Instead, it gives you a high-level growth trend, how fast the number of operations increases relative to the input size.

For example: if your input doubles, does your algorithm take twice as long? Ten times as long? Or does it barely change at all?

Big O helps you answer those questions without even running the code, so you can choose the most efficient algorithm for large inputs.

Here is how the common complexities compare as the input n grows. The ones near the top barely react to bigger inputs, while the ones near the bottom blow up fast.

Big O is machine-independent. It doesn’t matter whether your code runs on a fast laptop or a slow server, the growth pattern stays the same.

The key variable that drives Big O is the input size n. As n increases, Big O helps you predict whether the algorithm will still be efficient or become impractical.

Let's go over the most common time complexities.

Even small differences in complexity (like O(n) vs. O(n log n)) add up quickly as n grows.

1. Constant Time – O(1)

This is the fastest and most efficient time complexity.

An algorithm is O(1) if it performs a fixed number of operations, meaning the execution time does not depend on the size of the input.

A classic example is accessing an element in an array by index.

It doesn’t matter if the array has 10 elements or 10 million, the time it takes to access an element stays exactly the same.

There’s no looping, no scanning. You jump directly to the value using its index.

2. Logarithmic Time – O(log n)

Next up is logarithmic time, or O(log n).

An algorithm runs in O(log n) time when every step reduces the problem size by a constant factor, most often by half.

This means the amount of work grows very slowly, even when the input becomes massive.

The most common example is binary search.

Consider a sorted array of 1 million elements. Instead of scanning linearly:

Each step discards half of the remaining data.

To put that into perspective, here is the maximum number of steps binary search takes for different input sizes.

Another example of logarithmic time is searching in a balanced binary search tree.

At each node, you eliminate half of the remaining subtree, just like binary search.

3. Linear Time – O(n)

Now let’s talk about linear time, or O(n).

An algorithm is O(n) when its running time grows directly in proportion to the size of the input.

If the input doubles, the number of operations also doubles.

A simple example is finding the maximum value in an array:

So with 10 elements, you do 10 comparisons.

With 1 million elements, you do 1 million comparisons.

Any algorithm that visits every element exactly once is linear time.

Other common examples of O(n) complexity include:

In general, when your algorithm has to look at each element at least once, whether it’s an array, a linked list, a tree, or any collection, you’re most likely dealing with O(n) time.

4. Linearithmic Time – O(n log n)

Next is O(n log n), also called linearithmic time.

Algorithms with O(n log n) time complexity combine two behaviors:

It’s often described as logarithmic splitting with linear merging.

The classic example is merge sort:

So you do n work across log n levels, and n × log n gives you O(n log n).

This complexity is slightly slower than linear time but still very efficient, and many fast sorting algorithms run in O(n log n).

5. Quadratic Time – O(n²)

Next up is quadratic time, or O(n²).

In an O(n²) algorithm, the number of operations grows proportionally to the square of the input size. So if you have n elements, you perform roughly n × n operations.

This typically happens when you have nested loops, where for each element you iterate over all the other elements.

Classic examples include simple sorting algorithms like:

All of them compare or swap elements in nested loops, leading to O(n²) behavior.

These algorithms are fine for small inputs, but they become painfully slow as n grows:

For n = 1,000, you’re doing around 1 million operations. And if n = 10,000, you’re looking at 100 million operations.

In coding interviews and wherever performance matters, you’ll often want to avoid O(n²) and look for ways to bring it down to O(n log n) or better.

That said, sometimes quadratic time is acceptable, especially when n is small or no better solution exists.

6. Exponential Time – O(2ⁿ)

Next is exponential time, or O(2ⁿ).

Exponential time algorithms usually appear when we try to solve a problem by checking every possible combination, often through brute force or backtracking.

Think of it as the opposite of binary search. Instead of eliminating half the work at each step, you double the work with each extra input element.

This happens in problems where each element can branch into multiple recursive calls.

A classic example is generating all subsets of a set (also called the power set). For each element, we make two recursive choices, include it or exclude it, leading to 2 × 2 × ... × 2 = 2ⁿ total combinations.

If the set has n elements, there are 2ⁿ possible subsets. That means just 30 elements give you over 1 billion subsets, and 40 elements give you over 1 trillion.

This kind of growth becomes unmanageable very quickly. Even a small increase in n makes the runtime explode.

The good news is that many exponential-time problems can be optimized using techniques like memoization or dynamic programming.

These techniques prevent us from recomputing the same subproblems, often reducing the time from O(2ⁿ) down to a much more practical polynomial time, which makes the solution usable on real inputs.

In general, exponential algorithms are fine only for very small inputs. For anything larger, you must either optimize or rethink the approach.

7. Factorial Time – O(n!)

Finally, we reach the steepest common complexity: factorial time, or O(n!).

This is what you get when an algorithm tries every possible arrangement of a set of n elements.

The number of possibilities grows faster than any other complexity we’ve seen.

By definition, n! (n factorial) means n × (n - 1) × (n - 2) × ... × 1, which gives:

Even at n = 15, the numbers are already in the trillions, which makes it completely impractical to compute.

A classic example of O(n!) is generating all permutations of a string.

If you have a string of length 10 and try to print every permutation, that’s already about 3.6 million arrangements. And going from n to n + 1 multiplies the work by n + 1, so a string of length 11 takes 11 times longer, and length 12 takes 12 times longer than that.

These kinds of brute-force solutions are mostly used for very small inputs. For anything larger, we rely on smarter techniques like dynamic programming, branch and bound, or heuristics to reduce the problem space.

Putting Them Side by Side

To see why complexity matters so much, here is roughly how many operations each one takes as the input grows. The numbers in the last two columns are where the difference becomes obvious.

The top three rows stay manageable no matter how large the input gets. The bottom two become impossible to compute well before the input reaches a few dozen elements.

So far, we’ve focused on time complexity, how fast an algorithm runs as input size grows.

But Big O also applies to memory usage, and that is called space complexity.

In interviews, you’ll often be asked to analyze both time and space complexity, because in real systems performance is about both speed and how much memory your solution consumes.

Space complexity tells you how much extra memory your algorithm uses in addition to the input itself.

This extra memory can come from:

Even if your algorithm is fast, it may still use more memory than it needs, which can be a serious problem in large-scale systems or environments with limited RAM.

Here are the common space complexities:

1) O(1): Constant Space

If you scan an array to find the maximum value, you only store one variable to track the current max.

So while the input size may grow, your extra space stays constant.

2) O(n): Linear Space

Now suppose you collect all even numbers from the array into a new list.

If half the numbers are even, that’s roughly n/2 elements, which still counts as O(n) space.

3) O(log n): Logarithmic Space

Recursive divide-and-conquer algorithms often use O(log n) space because each recursive call adds a frame to the call stack, and the recursion depth grows logarithmically with the input.

For example, recursive binary search halves the search range on each call. On an array of size n, the call stack reaches a maximum depth of log₂n, so the extra space is O(log n).

4) O(n²): Quadratic Space

Storing a full matrix (like an adjacency matrix or DP table) of size n × n takes O(n²) space.

Here is a 4×4 adjacency matrix as an example. It holds 4 × 4 = 16 entries, and a larger n × n matrix scales the same way: storage grows with the square of n.

5) A Hidden Source of Space: The Recursion Call Stack

Space complexity isn’t only about the extra data structures you create. Recursion also consumes memory through the call stack, and this cost is easy to overlook because you never allocate it yourself.

Every recursive call adds a new frame to the stack, and that frame stays there until the call returns. So the extra space a recursive algorithm uses is set by its maximum recursion depth, which is how many calls are active at the same time. That depth depends entirely on the shape of the recursion.

The earlier binary search example showed this: it recurses only log₂n deep, so it uses O(log n) stack space. Other recursion shapes give very different results.

For example, the naive recursive Fibonacci solution branches into two calls each time. It takes O(2ⁿ) time, but the stack only ever holds one root-to-leaf path of calls at a time, so its space is O(n).

Depth First Search (DFS) on a tree depends on the height h of the tree:

Let's talk about how to calculate the complexity of a piece of code.

The simplest way is to break your code down into parts and analyze each part separately.

Rule 1: Add Complexities of Sequential Operations

If your algorithm performs one block of work after another, you add their time complexities.

Consider code with two separate, sequential loops:

The total runtime is the time for Block A plus the time for Block B, which comes out to O(m) + O(n²). Here m and n are independent inputs, so neither term dominates the other and we keep both. If both blocks depended on the same n, this would simplify to O(n²) using Rule 4 below.

Rule 2: Multiply Complexities of Nested Operations

If your algorithm has a nested loop with the outer loop running n times and the inner loop running m times, the total complexity is O(n × m).

Rule 3: Drop Constant Factors

This rule states that we can ignore any constant multipliers in a Big O expression.

When you derive a time complexity expression, you may end up with something like O(2n + 5) or O(n² + n + 10).

Big O captures how fast your algorithm grows with input, not the exact number of steps.

Whether your algorithm takes n steps or 5n steps, both grow linearly as n increases, so the constant multiplier doesn’t affect the growth trend. If you double the input, the runtime for both will roughly double.

So we drop constant factors:

Rule 4: Drop Lower-Order Terms

If your final expression has multiple terms, you keep only the one that grows the fastest, the dominant term, and drop the rest.

Why? Because as n becomes very large, slower-growing terms become insignificant.

Consider the expression O(n² + n + 100) with n = 1,000,000 (one million).

At scale, the lower-order terms barely make a dent in the overall growth. So we only keep the term that dominates.

Here are more examples:

Now that you understand what Big O notation means and how it helps us describe the growth rate of algorithms, it’s time to go one step deeper.

Big O gives us an upper bound. It tells us how fast an algorithm’s running time can grow in the worst case.

But not every input triggers that worst-case behavior. Some inputs make an algorithm run much faster, while others make it much slower.

So how do we capture that difference?

That’s where best, worst, and average case complexity comes in, a more nuanced way to describe how an algorithm behaves across different kinds of inputs.

In the next chapter, we’ll explore what these three cases mean, how to identify them, and why they matter when analyzing real-world algorithms.