Free lesson · DSA Mastery - Interview Prep, End to End

Introduction

Easy7 min readdsabig-o-notation

Introduction to Big O Notation

Big O notation is the vocabulary engineers use to describe how an algorithm's running time or memory usage grows as the input gets larger. When someone says "this is O(n log n)," they mean: as the input doubles, the work roughly doubles plus a small extra factor. When they say "this is O(n²)," they mean: as the input doubles, the work quadruples.

The notation looks like math, and underneath it is math. But for interview purposes, you do not need to be a mathematician. You need to know enough to reason about algorithmic efficiency, compare approaches, and communicate clearly with other engineers. That is what this section is about.

Why Big O Matters

Imagine you write code to find duplicates in an array. You test it on 100 elements - works fine, runs in milliseconds. You ship it. A year later, the array has 1 million elements, and the code takes hours. You did not write a broken algorithm. You wrote an algorithm whose running time grew faster than you expected.

Big O is the tool engineers use to predict this kind of thing before it happens. The algorithm in the example above was almost certainly O(n²) - checking every pair. For 100 elements, that is 10,000 operations: nothing. For 1 million elements, that is 1 trillion operations: hours. The difference is not in the code; it is in how the code scales.

In interviews, the same logic applies. When the interviewer says "now do it in O(n)," they are not asking for cleaner code or a different language - they are asking for a fundamentally different approach that does not multiply work by input size when it does not need to.

What Big O Actually Describes

Big O describes the upper bound on how a function grows as its input grows. The "O" stands for "order of." The "n" represents the size of the input.

When we say an algorithm is O(n), we mean: as the input size n grows, the running time grows at most linearly. Doubling n approximately doubles the work. When we say O(n²), doubling n approximately quadruples the work. When we say O(log n), doubling n adds a fixed amount of work - usually one extra iteration.

There are a few important things Big O does NOT describe:

• It is not the exact runtime. "O(n)" does not mean "exactly n operations." It means "the runtime grows linearly with n, ignoring constant factors."
• It is not platform-specific. An O(n) algorithm is O(n) on any machine, fast or slow. The constant time per operation changes; the growth rate does not.
• It does not tell you which algorithm is fastest in practice. An O(n²) algorithm can be faster than an O(n log n) algorithm for small inputs because constant factors matter. Big O is about asymptotic behavior - what happens as n gets large.

This last point is important. Big O is a long-run prediction, not a microbenchmark. For small data, "worse" Big O can outperform "better" Big O. For large data, Big O always wins.

The Common Complexity Classes

Most algorithms you encounter fall into a small number of complexity classes. Knowing them by name and recognizing them in code is most of what Big O competence looks like.

graph LR
    A["O(1)<br/>Constant"] --> B["O(log n)<br/>Logarithmic"]
    B --> C["O(n)<br/>Linear"]
    C --> D["O(n log n)<br/>Linearithmic"]
    D --> E["O(n²)<br/>Quadratic"]
    E --> F["O(2ⁿ)<br/>Exponential"]
    F --> G["O(n!)<br/>Factorial"]
    
    style A fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style G fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This diagram shows the common complexity classes ordered from fastest to slowest growth. O of one and O of log n are excellent and shown in green. O of n and O of n log n are good and shown in indigo. O of n squared is acceptable for moderate inputs and shown in amber. O of two to the n and O of n factorial are exponential and factorial growth, shown in red, and are usually unacceptable for any meaningful input size.

Let us go through them one at a time.

O(1) - Constant Time

The work does not depend on the input size. Looking up a key in a hash map, accessing an array element by index, or reading the length of a list are all O(1). Doubling the input changes nothing about the runtime.

This is the gold standard. When you can solve a problem in O(1), you have basically eliminated input size as a factor.

O(log n) - Logarithmic Time

The work grows extremely slowly. Doubling the input adds one constant unit of work. Binary search is the canonical example - searching a sorted array of a billion elements takes roughly 30 comparisons.

Logarithmic algorithms feel almost as good as constant time for any reasonable input. They appear whenever you can repeatedly halve the search space (binary search, balanced binary trees, divide-and-conquer with logarithmic recursion depth).

O(n) - Linear Time

The work grows in proportion to the input. Reading every element of an array is O(n). Doubling the input doubles the work.

Linear is usually the goal for problems that require touching every element. You cannot do better than linear if the problem fundamentally requires looking at all the data - but you should never do worse without good reason.

O(n log n) - Linearithmic Time

Slightly worse than linear, much better than quadratic. This is the complexity of efficient comparison-based sorting algorithms (merge sort, heap sort, the average case of quick sort). It is also the complexity of many divide-and-conquer algorithms.

For practical purposes, O(n log n) is "almost linear." A million elements takes about 20 million operations - fast on modern hardware.

O(n²) - Quadratic Time

The work grows with the square of the input. Doubling the input quadruples the work. Nested loops over the same input usually produce O(n²) behavior.

Quadratic is acceptable for small inputs (n < 10,000 or so) but becomes painful quickly. A million-element O(n²) algorithm is a trillion operations - minutes or hours of compute. In interviews, an O(n²) brute force is usually a starting point, and the interviewer wants you to improve on it.

O(2ⁿ) - Exponential Time

The work doubles for every additional input element. Many naive recursive algorithms (like the unmemoized Fibonacci) are exponential. Generating all subsets of a set is O(2ⁿ).

Exponential algorithms are usable only for very small inputs. n = 20 is 1 million operations, n = 30 is 1 billion, n = 40 is unreachable. If you find yourself with an exponential algorithm in an interview, you almost certainly need memoization or dynamic programming to bring it down.

O(n!) - Factorial Time

The worst common class. Generating all permutations of a set is O(n!). The factorial grows even faster than exponential.

Factorial algorithms are usable for n < 12 or so. Beyond that, they are completely impractical. If your algorithm is O(n!), the interviewer expects you to have a strong reason - usually you cannot avoid it, like in problems that genuinely require checking all orderings.

Reading Big O from Code

Once you know the classes, the next skill is reading them out of code. A few patterns map directly.

Single loop over the input is O(n).

for (int i = 0; i < n; i++) {
    // constant work
}

n iterations, constant work each -> O(n)

Nested loop, both over input, is O(n²).

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // constant work
    }
}

n * n iterations -> O(n²)

Loop that halves the search space is O(log n).

while (left <= right) {
    int mid = (left + right) / 2;
    if (target < arr[mid]) right = mid - 1;
    else left = mid + 1;
}

Each iteration halves the range -> O(log n)

Recursion with two child calls and constant work is O(2ⁿ).

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Each call spawns two more -> O(2ⁿ)

The patterns are not always obvious. Sometimes a single loop is actually O(n log n) because it does logarithmic work each iteration. Sometimes two nested loops are O(n) because the inner loop's bounds shrink as the outer loop progresses. Reading complexity is a skill that improves with practice - and the rest of this section helps build it.

Dropping Constants and Lower-Order Terms

A subtle but important rule: Big O drops constants and lower-order terms.

An algorithm that takes 3n + 5 operations is O(n), not O(3n + 5). The constants 3 and 5 are dropped because Big O is about how the function grows, not its exact value at any point. As n gets large, the difference between 3n and n is negligible compared to the growth rate.

Similarly, n² + 100n + 50 is O(n²). The lower-order 100n and the constant 50 are dropped because n² dominates as n grows.

Some specific consequences:

• An algorithm that does 5 separate linear scans is O(n), not O(5n). The constant is dropped.
• An algorithm that is O(n) plus O(log n) is O(n). The slower-growing term dominates.
• An algorithm that does O(n) work, then O(n²) work, then more O(n) work, is O(n²). The dominant term wins.

The rule is: keep only the highest-order term, and drop its coefficient. 5n³ + 200n² + log n becomes O(n³).

This is what makes Big O so useful for high-level reasoning. You do not need to count exact operations; you just need to identify the dominant term.

What to Take From This Section

Big O is the universal language of algorithmic efficiency. The remaining topics in this section build on this foundation:

• Best, Worst, and Average Complexity (Topic 3.2) - Algorithms can behave differently on different inputs. We distinguish the cases.
• Amortized Analysis (Topic 3.3) - Some operations are usually O(1) but occasionally expensive. Amortized analysis captures the long-run average.
• Recurrence Relations (Topic 3.4) - A formal way to describe recursive algorithms' complexity.
• Master Theorem (Topic 3.5) - A shortcut for solving common recurrence relations without doing the math from scratch.

Together, these topics give you the vocabulary and tools to reason about any algorithm's efficiency. From here on, every algorithm in the course will have a complexity analysis section, and the analysis will assume you understand the foundations laid here.

If you remember nothing else from this introduction, remember this: Big O is about growth, not exact values. It is the right tool for predicting how an algorithm will behave on inputs much larger than the ones you have tested. And it is the language interviewers use when they ask "can you do better?"

Back to DSA Mastery - Interview Prep, End to End