What is Big O and why is it so important?

A fundamental tool for analyzing algorithm efficiency and predicting how they behave at scale

When we think about the quality of a computer program, we often focus on its speed: how long does it take to launch Visual Studio Code? How fast does Instagram load when you open the app? Why does Netflix play a video instantly while YouTube sometimes keeps buffering? However, the true measure of an efficient algorithm is not just how fast it runs once, but how well it scales as the amount of data grows dramatically.

This is where Big O Notation (O) comes into play. Big O Notation is a fundamental tool in computer science that provides a simplified analysis of an algorithm’s efficiency. It allows us to compare algorithms and predict the impact that increasing input size (N) will have on runtime, without worrying about machine-specific details.

Why Not Simply Measure Speed?

In the real world, code execution speed depends on many factors: the type of processor, cache memory, programming language, and even whether other applications are running simultaneously.

To compare algorithms fairly and independently of the machine, we need a theoretical framework that allows us to evaluate the intrinsic efficiency of algorithms, ignoring external factors such as hardware, operating system, or the language’s specific implementation.

There are several theoretical frameworks for algorithm analysis: the Turing Machine Model (focused on theoretical computability), the Boolean Circuit Model (used in circuit complexity), and the PRAM Model (Parallel Random Access Machine, for parallel algorithms). However, for practical analysis of sequential algorithms, we use the RAM Model.

The Simplified RAM Model

This Random Access Machine model simplifies reality by making 3 key assumptions:

1. Primitive Instructions: It assumes that basic arithmetic operations (add, subtract, multiply, divide), data movement (load, store, copy), and control structures (loops, function calls) take a constant amount of time (one time unit).
2. Execution Time: We define execution time as the number of steps or primitive operations executed.
3. Input Size (N): The computation time generally grows with the input size. For example, in a sorting algorithm, N is the number of elements to sort.

The Asymptotic Focus

The goal of Big O notation is to observe the algorithm’s asymptotic efficiency. This means we are mainly interested in how runtime behaves when the input size (N) becomes extremely large.

To focus on real growth and simplify the analysis, we apply two crucial rules:

Rule 1: Discard Constants

Big O notation ignores constants.

Consider a simple algorithm that searches for a specific element in an array:

function searchElement(array, element) {
  // 1 operation: initialize i
  // N operations: compare array[i] === element
  // N operations: increment i
  // N operations: evaluate condition i < array.length
  // 1 operation: return

for (let i = 0; i < array.length; i++) {
if (array[i] === element) {
return i;
}
}
return -1;
}

In the worst case, this algorithm executes roughly 3N + 2 operations (3N inside the loop + 2 outside). However, in Big O we simplify this to O(N), ignoring both the constant 3 and the +2 term.

Why? Because as N becomes very large (1 million, 10 million), the difference between 3N and N becomes insignificant in terms of growth rate. Big O focuses on measuring how algorithms scale, so it prioritizes growth rate over specific implementation details.

Rule 2: Discard Lower-Order Terms

In a function describing an algorithm’s runtime, terms that grow more slowly become insignificant as N increases.

Imagine an algorithm that finds all pairs of duplicate elements in an array:

function findDuplicatePairs(array) {
  // Outer loop: N operations
  for (let i = 0; i < array.length; i++) {
    // Inner loop: N operations per outer iteration
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] === array[j]) {
        console.log(`Duplicate found: ${array[i]}`);
      }
    }
  }

// Additional operations: sort the array at the end
array.sort(); // N log N operations

// Final operations
console.log("Search complete"); // 1 operation
}

Analyzing the operations:

• Nested loops: N² operations (dominant)
• Sorting: N log N operations (O(N log N) for efficient algorithms like merge sort, we’ll cover this in future posts)
• Constant operations: 1 operation

The complete function would be: T(N) = N² + N log N + 1

But observe what happens with large values:

• If N = 1,000: N² = 1,000,000 vs N log N ≈ 10,000 vs 1 = 1

  • Total: 1,010,001 operations (N² contributes 99.01%)

• If N = 100,000: N² = 10,000,000,000 vs N log N ≈ 1,660,000 vs 1 = 1

  • Total: 10,001,660,001 operations (N² contributes 99.98%)

The term N² completely dominates, so we simplify to O(N²). Lower-order terms become negligible in the face of quadratic growth.

Emphasis on the Worst Case

When analyzing algorithms, we generally focus on the worst case.

The worst case occurs when the input causes the algorithm to perform the maximum number of steps. For example, in a linear search in an array, the worst case is when the element we’re looking for is at the end of the array or doesn’t exist at all, forcing the algorithm to check every element.

The worst case is crucial because it gives us an upper bound. Knowing that an algorithm will never take longer than a certain time provides a performance guarantee, which is far more useful than the best case (often irrelevant) or the average case (which can be hard to calculate).

Asymptotic Notations: O, Ω, and Θ

From an academic and mathematical perspective, there are three formal notations to describe algorithm efficiency. Academia uses these concepts to set precise limits on the behavior of the functions that describe runtime:

A. Big O (O): The Upper Bound

Big O (O) is used to establish only an upper bound. We say that a time function f(N) is O(g(N)) (read: f is “big oh” of g) if the growth rate of f(N) is at most as fast as g(N).

Formal definition: f(N) = O(g(N)) if there exist positive constants C and N₀ such that 0 ≤ f(N) ≤ C · g(N) for all N ≥ N₀.

Practical example: It’s like saying “the car trip to the beach takes at most 3 hours.” You might arrive in 2 hours if there’s no traffic, but it will never take more than 3 hours. Big O gives us that upper-limit guarantee.

• Application: Strictly speaking, Big O sets an upper bound, but as we’ll see later, in the industry we use this term more broadly.

B. Big Omega (Ω): The Lower Bound

Big Omega (Ω) is used to establish only a lower bound. We say that f(N) is Ω(g(N)) if the growth rate of f(N) is at least as fast as g(N).

Formal definition: f(N) = Ω(g(N)) if there exist positive constants C and N₀ such that 0 ≤ C · g(N) ≤ f(N) for all N ≥ N₀.

Practical example: It’s like saying “I need at least 1 hour to prepare dinner.” It might take 1 hour or more (if it’s a complex recipe), but never less than 1 hour. Big Omega assures us of the minimum time required.

C. Big Theta (Θ): The Tight Bound

Big Theta (Θ) provides both an upper and lower bound (a tight asymptotic bound).

Formal definition: f(N) = Θ(g(N)) if the conditions of both Big O and Big Omega hold: there exist positive constants C₁, C₂, and N₀ such that C₁ · g(N) ≤ f(N) ≤ C₂ · g(N) for all N ≥ N₀.

Practical example: It’s like saying “my morning routine takes exactly between 45 and 60 minutes.” We have both a lower bound (never less than 45 min) and an upper bound (never more than 60 min). Big Theta gives us the exact growth range.

• Meaning: If we say that a program’s runtime is Θ(N²), we are stating that its dominant part is exactly the N² component.

Industry vs Academic Perspective

There are important differences between how academia defines algorithmic efficiency and how the software industry interprets it in practice. These differences reflect different needs: academia seeks mathematical precision, while industry seeks practical tools for design decisions.

Spreading the Cost (Amortization)

Although the academic definition of Big O focuses on the worst case, in industry we often “amortize” that worst case by spreading its cost over multiple operations. Amortized analysis doesn’t make the algorithm run faster; it’s a form of accounting that helps show that the algorithm’s average efficiency is better than a single worst case suggests.

Amortization means taking a large cost (which occurs rarely, perhaps at the beginning) and spreading it over time or a number of operations.

Dunkin Donuts example: If it costs $1 million to open a franchise (initial cost) and $1 to make each donut:

• The first donut costs $1,000,001.
• But if we assume we’ll make 1 million donuts, we can spread the initial $1 million cost across all of them. The amortized cost is then $1 (actual cost) + $1 (share of the initial fee), making each donut cost $2 on average.

“Big O” in the Industry

When developers talk about “Big O,” the concept they use is closer to the academic definition of Big Theta (Θ) than to the strict definition of Big O. When we say that an algorithm is O(N²), we typically mean that its complexity is quadratic, not just that it has a quadratic upper bound.

Example: If a developer says “QuickSort is O(N log N),” they are really communicating that QuickSort’s typical complexity is N log N (closer to Θ(N log N)). QuickSort is a sorting algorithm that works by recursively dividing the array into smaller parts. In most cases, it efficiently divides the data (log N divisions) and processes each element once (N operations), resulting in N log N total operations.

However, academically it would be more precise to say that QuickSort is O(N²) in the worst case (when the data is ordered in such a way that divisions are very unbalanced, processing almost all elements at each level), but Θ(N log N) on average. In industry, we use “O(N log N)” to refer to its expected behavior, ignoring the rare worst case.

Common Complexity Hierarchy

The efficiency of an algorithm is classified according to its order of growth. Here are the most common ones, ordered from fastest/most efficient to slowest/least efficient:

Practical Growth Example

Imagine we double our input size (N):

• O(1): Time doesn’t change.
• O(N): Time doubles.
• O(N²): Time quadruples (proportional to the square of the data).

For example, in a Bubble Sort with 10,000 elements it took 362 ms, but with 20,000 elements it took 1,612 ms (roughly 4 times more), proving that N² order should be avoided.

Note on Logarithms

If you see a complexity like O(N log N), don’t worry about the logarithm’s base (whether it’s log₁₀, log₂, or ln). In Big O notation, the base of the logarithm doesn’t matter, since logarithmic functions with different bases are asymptotically equal (they differ by a constant), and constants are ignored.

Conclusion and References

Big O Notation (O) is the fundamental tool for any developer who wants to understand and design scalable algorithms. By discarding constants and focusing on the dominant growth term (like N² instead of 45N³ + 20N² + 19) and prioritizing the worst case, we can measure asymptotic efficiency, that is, how well an algorithm scales as the input size (N) becomes extremely large. This theoretical perspective provides long-term performance guarantees without being affected by the machine’s specific details or the programming language we use.

If you want to delve deeper into these topics of algorithmic analysis, asymptotic limits (Ω, Θ), and efficiency, you can check out the following references that served as the basis for this article:

• Harvard CS50 – Asymptotic Notation (video)
• Big O Notations (general quick tutorial) (video)
• Big O Notation (and Omega and Theta) – best mathematical explanation (video)
• Skiena (video)
• UC Berkeley Big O (video)
• Amortized Analysis (video)
• Computational Complexity: Section 1
• Computational Complexity: Section 2
• Big-O Algorithm Complexity Cheat Sheet
• [Review] Analyzing Algorithms (playlist) in 18 minutes (video)