Big-O Notation

Counting steps, not seconds

Big-O does not measure time in seconds. Seconds depend on your laptop, your compiler, and whether Spotify is running. Instead, it counts how the number of basic steps grows as the input size grows. We call the input size n: the length of an array, the number of characters in a string, the number of users in a list.

Here is the key mental shift: we only care about the growth trend, not exact counts. If one algorithm takes 3n + 5 steps and another takes n steps, both double their work when n doubles, so both are O(n), pronounced "order n" or "linear time". Constants and small terms get dropped because for large n they stop mattering. What matters is the shape of the curve: does the work grow in a straight line, a gentle curve, or an explosion?

The common complexity classes

You will meet the same handful of growth rates over and over, from fastest to slowest. O(1), constant time, means the work does not depend on n at all, like grabbing an array element by index. O(log n), logarithmic time, means the work grows very slowly because each step cuts the problem in half, that is the phone-book trick, formally called binary search. O(n), linear time, means you touch each element once, like a simple loop. O(n log n) is the cost of good sorting algorithms. O(n squared), quadratic time, usually means a loop inside a loop. Every element compared against every other element. Beyond that live O(2 to the n) and worse, which only work for tiny inputs.

To feel the difference, take n = 1,000,000. O(log n) is about 20 steps. O(n) is a million. O(n log n) is about 20 million, still fine. O(n squared) is a trillion steps, which is minutes to hours. In an interview, moving a solution from O(n squared) to O(n) or O(n log n) is often the whole point of the question.

int[] nums = {4, 8, 15, 16, 23, 42};

int first = nums[0];

int sum = 0;
for (int x : nums) {
    sum += x;
}

int pairCount = 0;
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        pairCount++;
    }
}

How to find the Big-O of your code

Reading complexity off code is mostly pattern matching. A single loop over n elements is O(n). Two loops one after another are O(n) + O(n), which we still call O(n). Remember, constants are dropped. A loop nested inside another loop, where both run n times, multiplies: O(n squared). A loop that halves its range each iteration, like binary search, is O(log n). Calling an O(n) helper inside an O(n) loop gives O(n squared), so watch out for hidden work. Methods like contains on a list are loops in disguise.

One more convention: Big-O usually describes the worst case. Searching an array for a value might get lucky and find it at index 0, but we say the search is O(n) because in the worst case we check everything. When someone asks "what is the complexity?", give the worst case unless they ask otherwise.

boolean contains(int[] nums, int target) {
    for (int x : nums) {
        if (x == target) {
            return true;
        }
    }
    return false;
}

Space complexity and the time-space trade

Big-O also measures memory. Space complexity counts the extra memory your algorithm allocates as n grows, not counting the input itself. A method that uses a few int variables is O(1) space no matter how big the array is. A method that copies the array, or builds a hash map with one entry per element, is O(n) space.

Many classic interview optimizations are a trade: spend memory to save time. A nested-loop duplicate check is O(n squared) time and O(1) space; adding each element to a set as you go is O(n) time and O(n) space. Being able to name both costs ("this is O(n) time, O(n) space") is exactly what interviewers listen for.

With this vocabulary in hand, you are ready to meet your first real data structure: the array, whose superpower is O(1) access to any element.

Frequently asked