What Is Big-O Notation? Time Complexity Explained Simply

If you are learning to code, you will hit Big-O notation the moment you start thinking about whether your code is fast enough. It looks intimidating — letters, parentheses, the occasional logarithm — but the idea underneath is simple, and it is more logic than mathematics. Big-O is a shared language for describing how an algorithm's workload grows as the amount of data grows. Get comfortable with it and you can compare two solutions on paper, predict which one will survive real-world scale, and answer the question every interviewer eventually asks.

What Big-O actually measures (growth, not seconds)

The most common beginner mistake is to read Big-O as a measure of time in seconds. It is not. The same code runs faster on a new laptop than an old phone, but its Big-O is identical on both. What Big-O measures is *growth*: if you double the size of the input, what happens to the amount of work? Does it double, stay flat, or explode? That relationship — input size versus operations — is the whole point of time complexity.

We write the input size as n. An algorithm that is O(n) does roughly n units of work; one that is O(n^2) does roughly n times n. Big-O also throws away constants and small terms, because they stop mattering as n gets large. O(2n + 5) is simply O(n). We care about the dominant shape of the curve, not the fine print.

The intuition behind it

Imagine you are looking for a name in a phone book. If you check every entry from the first page to the last, the work grows in step with the size of the book — twice the pages, twice the work. That is linear, O(n). But if you open the book in the middle, decide which half the name is in, and repeat, you halve the problem every step. A book twice as thick costs you just one extra step. That is logarithmic, O(log n), and it is why a phone book is sorted.

A reliable mental test: ask "if the input gets ten times bigger, does the work get ten times bigger, a hundred times bigger, or barely change?" Ten times is linear, a hundred times is quadratic, barely changing is logarithmic.

The common complexity classes

You only need a handful of classes to describe almost everything you will write. Here they are, slowest-growing first, each with a plain example.

• O(1) — constant. The work never changes, no matter the input. Looking up a value in a dictionary by its key, or grabbing the first item in a list.
• O(log n) — logarithmic. The work grows very slowly because each step throws away half the data. Binary search in a sorted list.
• O(n) — linear. One pass over the data. Finding the largest number in an unsorted list — you must look at every element once.
• O(n log n) — linearithmic. Slightly worse than linear, the sweet spot for good sorting. Merge sort and the sort built into most languages live here.
• O(n^2) — quadratic. Work grows with the square of the input, usually from a loop inside a loop. Comparing every item to every other item.
• O(2^n) — exponential. Work doubles with each extra input. Trying every possible combination, like naive brute-force on a password. Avoid this whenever you can.

How fast the gap grows

Numbers make the difference visceral. Here is roughly how many operations each class needs as n climbs.

Notice that at a million items, O(log n) still finishes in about twenty steps while O(n^2) needs a trillion. Code that felt instant in testing can lock up entirely at scale, and the table is exactly why.

How to spot the complexity in code

You rarely need to do arithmetic — you read the structure. A single loop over the input is one pass, so it is O(n). A loop nested inside another loop, both over the input, multiplies — n times n — so it is O(n^2). And anything that halves the search space each step, like binary search, visits about log n elements rather than n, so it is O(log n).

The shortcut: one loop over the data is usually O(n), a loop inside a loop is usually O(n^2), and dividing the problem in half each step is usually O(log n). This is the same kind of structured reasoning that underpins the math you actually need for programming — pattern, not heavy calculation.

Best, average, and worst case

An algorithm can behave differently depending on the data. Searching a list item by item finds the target on the first try in the *best* case — O(1) — but might have to check every element in the *worst* case, O(n). When people quote a single Big-O, they almost always mean the worst case, because that is the guarantee you can rely on. It is the answer to "how bad can this get?", which is exactly what you want to know before something ships.

A word on space complexity

Big-O is not only about time. Space complexity uses the same notation to describe how much extra memory an algorithm needs as the input grows. An algorithm that sorts a list in place uses O(1) extra space; one that builds a brand-new copy uses O(n). On large datasets or memory-constrained devices, the space cost can matter as much as the time cost, and interviewers often ask for both.

Why it matters in interviews and real code

In a technical interview, a working solution is only half the answer. The follow-up is always "what is the time complexity, and can you do better?" Being able to say "this is O(n^2), but sorting first makes it O(n log n)" is what separates a candidate who memorised a solution from one who understands it. The same skill shows up daily on the job: choosing a dictionary lookup over a list scan, or a better sort, is the difference between a feature that scales and one that times out. If you are working toward a developer role or planning to become an AI engineer, complexity reasoning is a foundation you will lean on constantly. And it all rests on a little clear logic — the same foundation you build when you learn to code from scratch.

Math Essentials & Logic for Programming builds exactly this kind of reasoning from the ground up: growth and functions, logarithms, proof and pattern, and the concrete logic behind algorithm analysis — with runnable examples and worked traces rather than abstract theory. No prior math background required.

$25 PDF · 7,588 pages

Math Essentials & Logic for Programming

A large source-backed programming resource edition with project cards, logic exercises, code/output layouts, and cited source paths.

Buy the PDF for $25 Preview pages