Back to Study Material Data Structures and Algorithms

Big O Notation

Big O notation is the standard way software engineers communicate about the efficiency of an algorithm. When someone says a function is O(n log n), they ar...

Big O Notation

Understanding the Most Important Tool for Measuring Algorithm Efficiency

Big O notation is the standard way software engineers communicate about the efficiency of an algorithm. When someone says a function is O(n log n), they are stating that the number of operations the function performs grows at most proportionally to n times the logarithm of n as the input size n increases.

Formally, a function T(n) is O(f(n)) if there exist positive constants c and n0 such that T(n) is less than or equal to c times f(n) for all n greater than n0. In plain terms: beyond some threshold input size, the true running time is always bounded above by a constant multiple of f(n). The constants c and n0 are not specified; only the shape of f(n) matters.

To find the Big O of a piece of code, look at the loops and recursive calls. A single loop iterating from 1 to n is O(n). Two nested loops each iterating to n give O(n^2). A loop that halves the remaining work each iteration, such as binary search, is O(log n). Combining independent code blocks: if block A is O(n) and block B is O(n^2), the overall complexity is O(n^2) because the dominant term wins.

Common simplification rules: drop constant multipliers (3n becomes n), drop lower-order terms (n^2 plus n becomes n^2), and use the highest-order term. These rules hold because Big O describes the growth rate, not a precise count.

Big O describes the worst case by convention unless stated otherwise. Saying quicksort is O(n^2) is technically correct for its worst case, but its average case is O(n log n). Carefully specifying the case avoids confusion.

Big O applies beyond sorting and searching. It describes the complexity of database queries, network protocol overhead, machine learning training, and compiler optimization passes. Understanding it lets you read documentation, research papers, and API specifications with a critical eye.

Worked example: finding all pairs in an array of n elements that sum to a target. Brute force: two nested loops, O(n^2). Optimized: sort the array in O(n log n), then use two pointers that converge from both ends in O(n). The total is O(n log n), a meaningful improvement for large n.

Interview tip: practice simplifying expressions before your interview. Given 4n^3 plus 7n^2 plus 100n plus 500, the Big O is O(n^3). Dropping constants and lower-order terms should be instant and automatic.