Big O Notation for Beginners: O(1), O(n), O(n squared), and O(log n) Explained

Growth, not stopwatch time

Big O is not about how many seconds something takes on your laptop. It is about how the work scales when the input gets larger. Two algorithms can both be O(n), yet one runs twice as fast on real hardware because of a smaller constant factor. Big O deliberately throws that constant away, because at large enough n the shape of the growth curve dominates any fixed multiplier.

The notation also keeps only the fastest-growing term. An algorithm that does 3n squared plus 5n plus 200 operations is simply O(n squared), because once n is large the squared term dwarfs the rest. This is why Big O is a coarse but powerful lens: it tells you the class of behavior, which is exactly what you need when deciding whether a solution will survive a hundred times more data.

The four common classes

O(1) is constant time: reading an array element by index or checking a hash map key takes the same effort whether the collection holds ten items or ten million. O(log n) is logarithmic: binary search halves the remaining data on each step, so searching a sorted list of a billion items takes only about thirty comparisons. Halving is the mirror image of the doubling you see when converting numbers between bases.

O(n) is linear: summing every element or scanning a list once touches each item exactly one time, so the work rises in a straight line with n. O(n squared) is quadratic and usually comes from nested loops, such as comparing every pair of items. At n of 1,000 that is a million operations; at n of 1,000,000 it is a trillion, which is where naive quadratic code quietly becomes unusable.

Why the class you pick matters

Complexity is what separates a prototype that works on your test file from software that survives production data. Sorting with an O(n squared) algorithm feels instant on a hundred rows and freezes on a million. Swapping in an O(n log n) sort keeps the same task under a second. The algorithm you choose, not the speed of the machine, sets the ceiling on how much data you can handle.

That said, Big O is asymptotic, meaning it describes behavior as n heads toward infinity. For small inputs a simpler O(n squared) routine can beat a fancy O(n log n) one with heavy overhead. The practical rule is to know the class of every core operation, then optimize the pieces that will actually see large n, rather than chasing constants on code that only ever handles tiny inputs.

Frequently asked questions

Is a lower Big O always faster?

Not for small inputs. Big O ignores constant factors, so an O(n log n) method with heavy setup can lose to a plain O(n squared) loop when n is tiny. The lower class wins once the input is large enough.

What is the difference between O(log n) and O(n log n)?

O(log n) does one logarithmic pass, like a single binary search. O(n log n) does a logarithmic amount of work for each of n items, which is the cost of efficient sorting algorithms like merge sort.

Does Big O cover memory too?

Yes. The same notation describes space complexity, how much extra memory an algorithm needs as n grows. An in-place sort may use O(1) extra space, while one that copies the data uses O(n).

Why do we ignore constants and lower terms?

Because at large n the fastest-growing term dominates everything else, and constants depend on hardware you cannot control. Dropping them yields a portable comparison of how algorithms scale, independent of any one machine.