9.2 Complexity Awareness

Once we have an algorithm, a natural question follows: how efficient is it. Some methods work quickly for small inputs but become slow when the input grows. Complexity awareness is the habit of thinking about how much time or effort an algorithm needs as the problem size increases.

Why efficiency matters

Consider the task of finding the largest number in a list. The method from the previous section checks each element once. If the list has 5 numbers, we do 5 comparisons. If it has 1,000 numbers, we do 1,000 comparisons. The work grows in a simple, predictable way.

Now imagine a different method. Suppose we compare every pair of numbers to decide which is larger. For 5 numbers, this already requires many comparisons. For 1,000 numbers, the number of comparisons becomes very large. The method still works, but it becomes impractical.

Two algorithms can give the same correct answer, but one may be much faster than the other.

Measuring the cost

We often measure the cost of an algorithm by counting how many basic steps it performs. These steps might be comparisons, additions, or other simple operations.

Let $n$ be the size of the input. For a list of numbers, $n$ is the length of the list.

• The “scan once” method uses about $n$ steps
• The “compare all pairs” method uses about $n^2$ steps

When $n$ is small, the difference may not matter. When $n$ is large, the difference is huge.

For example:

• If $n = 10$, then $n = 10$ and $n^2 = 100$
• If $n = 1{,}000$, then $n = 1{,}000$ and $n^2 = 1{,}000{,}000$

The second method grows much faster.

A simple search example

Suppose you want to find a number in a sorted list, such as

One method is to check each element from left to right. This may require checking every element.

A better method is to use the structure of the list. Start in the middle. If the target is smaller, look only in the left half. If it is larger, look in the right half. Repeat this process.

Each step cuts the problem roughly in half. This makes the search much faster for large lists.

Growth, not exact counts

In practice, we care less about exact step counts and more about how the number of steps grows.

An algorithm that takes $2n$ steps and one that takes $3n$ steps behave similarly as $n$ grows. Both grow linearly. An algorithm that takes $n^2$ steps grows much faster.

This idea leads to grouping algorithms by their growth rates, such as linear, quadratic, or logarithmic. These categories help us compare methods without focusing on small details.

Trade-offs

Sometimes a faster algorithm uses more memory. Sometimes a simpler algorithm is easier to understand but slower. There is often no single best solution in all situations.

For small inputs, a simple method may be good enough. For large inputs, efficiency becomes critical.

A practical habit

When you design or use an algorithm, ask:

How does the work grow as the input grows Does the method scale to large problems Is there a simpler or faster approach

Complexity awareness does not require advanced mathematics. It begins with careful observation of how many steps an algorithm performs and how that number changes with input size.