Time complexity

A computer works through a task in individual steps. How many steps it needs almost always depends on how much data it receives. A name in a list of ten entries is found quickly, while in a list of ten million it takes longer. Time complexity describes exactly this relationship: it states how strongly the effort grows as the amount of data grows. So it doesn’t measure seconds, but rather the growth behavior. This allows two approaches to be compared without even trying them out on a computer.

Why ten times more data rarely means ten times more time

Computers get faster every year, but data volumes grow even faster. That’s why raw speed doesn’t decide whether a program is usable. What matters is how it reacts to more data. A procedure whose effort quadruples when the data volume doubles goes unnoticed in small tests. In real operation with millions of entries, it collapses.

An example makes this tangible. If you sort a list by comparing every element with every other element, you need around a million comparisons for 1,000 elements. A good sorting method manages with about 10,000 comparisons. With 1,000 elements, you barely notice the difference. With a million elements, the poor method is practically unusable, while the good one finishes in a fraction of a second.

A common misconception: poor time complexity cannot be compensated for by better hardware. A computer twice as fast halves the time exactly once. A better procedure, on the other hand, changes the curve itself and takes effect again at every data volume.

What the big O means

Experts write time complexity using a capital O and the data volume n. O(n) means: the effort grows proportionally to the data volume. Ten times more data means ten times more work. This applies, for example, when going through an unsorted list completely once.

O(n²) means: with ten times more data, the effort grows to a hundred times as much. This happens when comparing every element with every other. O(log n) is the pleasant case: the effort grows only very slowly. This is how searching in a sorted directory works, where the search range is repeatedly halved. Out of a million entries, you find the right one in about twenty steps.

What matters is what this notation deliberately leaves out. Constant factors and small additional steps are ignored. An O(n) procedure can be slower than an O(n²) procedure for small data volumes. Big-O notation only describes who wins with large volumes. Usually, the worst case is also given, so as to have a reliable upper bound.

Time complexity in AI models and in job interviews

In language models, this topic arises at a very concrete point. The most important building block of these models compares every word of an input with every other word. This is a classic O(n²) case. If you double the length of the text, the computational effort quadruples. That’s why it was long expensive to present a chatbot with an entire book.

This is precisely why research groups are working on methods that shortcut this comparison. When news reports that a model now processes a context window of a million characters, such an improvement is almost always behind it. The topic is also omnipresent in databases: an index ensures that a search doesn’t run through the entire table, but finishes in a few steps.

For programmers, time complexity is basic knowledge. In job interviews at tech companies, the question about a solution’s runtime is standard. Anyone who only delivers a working answer but can’t say how it scales with a million records has only half-solved the task.