Time Complexity

Why not just measure runtime?

The most direct way to compare two algorithms seems obvious: implement both, run them on the same computer, and see which one finishes faster. But that comparison depends on the processor, the compiler, the programming language, the operating system, and even what else is running on the machine at that moment. Run the same code on a faster computer and the "better" algorithm can change.

To compare algorithms in a way that holds regardless of hardware, we instead study how the number of basic operations grows as the input gets larger. This is what time complexity measures.

We usually write this as T(n), where n is the input size.

Counting operations

Given a piece of code, how many operations does it perform?

for (i = 0; i < n; i++)
    printf("DATA STRUCTURE");

The loop body executes approximately n times, so T(n) is proportional to n. We describe this using Big-O notation as O(n), read "Big-O of n". For now, think of O(...) as a way to describe how the amount of work grows as n grows. The precise mathematical definition, where Big-O actually represents an upper bound rather than just "the growth rate", is covered in a later topic (asymptotic notations).

This raises a natural question: what exactly counts as "one operation"? It is not about counting individual machine instructions like additions or comparisons one by one, though you can if you want to see why the constants stop mattering. Take a slightly busier loop:

for (i = 0; i < n; i++)
    sum = sum + arr[i];

Count every basic step separately:

• comparison (i < n): runs n + 1 times (n times to allow entry, once more to detect the end and exit; e.g. for n = 3: checks at i = 0, 1, 2 pass, then i = 3 fails and stops the loop, 4 checks total)
• increment (i++): runs n times
• array access (arr[i]): runs n times
• addition (sum + arr[i]): runs n times
• assignment (sum = ...): runs n times

Add them up: T(n) = (n + 1) + n + n + n + n = 5n + 1. For large n, the constant multiplier 5 and the +1 barely matter, doubling n still roughly doubles T(n) either way, so we describe the growth as O(n). Exactly why constants and smaller terms get dropped when naming the growth rate is covered further down, in "Ignore lower-order terms". For now, the important part is: we are not trying to get an exact operation count, only how that count changes as n grows.

Common growth rates

O(1): constant time

x = a[10];

No matter how large the array is, one direct access is performed. Input size has no effect on the amount of work.

O(n): linear time

for (i = 0; i < n; i++)
    printf("%d", a[i]);

Work grows in direct proportion to n. Double the input and the work roughly doubles.

O(n²): quadratic time

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        printf("*");

The outer loop runs n times. For each of those, the inner loop also runs n times. Total work: n x n = $n^2$ operations. Nested loops over the same input are the most common source of quadratic time.

O(log n): logarithmic time

Logarithmic time shows up whenever the problem size is repeatedly cut down by a fixed factor, most often halved, at each step, rather than processed one element at a time.

n -> n/2 -> n/4 -> n/8 -> ... -> 1

The question is: how many times can n be halved before it reaches 1? We stop at 1 because that is the smallest meaningful size left, a single remaining element with nothing left to search or divide further. Solving $n / 2^k = 1$ gives $k = \log_2(n)$, so the number of halvings, and therefore the number of steps the algorithm takes, grows logarithmically, not linearly, with n. Binary search is the classic example: each comparison eliminates half of the remaining elements, so it takes about $\log_2(n)$ comparisons to narrow down to one.

O(n log n)

This appears when an algorithm does O(log n) work for each of n items, rather than O(log n) work just once. The clearest example is an efficient sorting algorithm like Merge Sort (don't worry about how it works yet, sorting algorithms are covered elsewhere): it processes all n elements, and at each of those n steps it does work proportional to log n, giving a total of $n \log n$.

Growth-rate hierarchy

Once you have classified an algorithm's time complexity, the natural question is: how do these growth rates compare to each other? Which is "faster"? Ranked from fastest-growing (worst) to slowest-growing (best):

For small n, the gaps between these barely matter. For large n, they become enormous. An O($n^2$) algorithm and an O(n) algorithm might both finish instantly for n = 10, but for n = 1,000,000 the O($n^2$) algorithm could take a million times longer.

Ignore lower-order terms

Real algorithms rarely produce a clean T(n) like n or $n^2$ on their own. They usually add up several pieces of work, for example $T(n) = 3n^2 + 5n + 10$, one term from a nested loop, another from a simple loop, another from fixed setup work. To name the growth rate of an algorithm like this, we use one rule: for large n, only the fastest-growing term matters.

$T(n) = 3n^2 + 5n + 10$

As n grows large, the $n^2$ term outgrows 5n and 10 so quickly that they become negligible in comparison, even though they are still technically part of the total. So we describe the growth as O($n^2$).

Similarly:

T(n) = 7n + 20

becomes O(n), because the n term dominates 20 for large n.

This is exactly the rule that let us go from T(n) = 5n + 1 to O(n) in "Counting operations" above: the constant multiplier and the +1 are lower-order details next to the n term, so they get dropped when naming the growth rate.

Quick recall

• Time complexity measures how work grows with input size, not actual seconds on one machine.
• T(n) counts basic operations as a function of n.
• O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O($n^2$) quadratic are the growth rates you will see most often.
• Nested loops over the same input typically produce O($n^2$); repeated halving produces O(log n).
• For a T(n) with multiple terms, only the fastest-growing term determines the O(...) classification.