Efficiency Means Counting Steps, Not Seconds

Algorithmic efficiency is about how the amount of work an algorithm does grows as the size of its input grows. The size of the input is usually called n: the number of items in a list, the number of users, the number of pixels. The key question is not "how many seconds does it take" but "how many steps does it take, and how does that step count change when n gets bigger."

We deliberately count steps instead of timing with a clock. A stopwatch measures the computer, the network, and what else the machine happens to be doing. Counting steps measures the algorithm itself, so the answer is the same on a fast laptop or a slow phone. To make this concrete, every example below uses a count variable that goes up by one each time the algorithm does a unit of work, and then prints the total.

# ONE loop over n items: about n steps (linear)
count = 0
for i in range(n):
    count = count + 1
print(count)

count <- 0
REPEAT n TIMES
{
    count <- count + 1
}
DISPLAY(count)

A single loop that runs n times does about n steps. We call this linear growth: double the input and you roughly double the work. If n is 5 the count is 5; if n is 500 the count is 500. Simple and predictable.

count = 0
for i in range(5):
    count = count + 1
print(count)

Nested Loops Multiply

Put one loop inside another and the work explodes. For every single pass of the outer loop, the inner loop runs all the way through. So an inner loop of n steps running inside an outer loop of n steps does about n times n steps. This is quadratic growth, often written n squared.

# NESTED loop: about n times n steps (quadratic)
count = 0
for i in range(n):
    for j in range(n):
        count = count + 1
print(count)

count <- 0
REPEAT n TIMES
{
    REPEAT n TIMES
    {
        count <- count + 1
    }
}
DISPLAY(count)

The single most common mistake is thinking nested loops add. They do not. Two loops side by side add (that is n plus n, which is 2n). Two loops nested multiply (that is n times n). Compare the nested version above with two separate loops below, which only reach 2n.

# TWO separate loops: steps ADD, not multiply
count = 0
for i in range(n):
    count = count + 1
for j in range(n):
    count = count + 1
print(count)

count <- 0
REPEAT n TIMES
{
    count <- count + 1
}
REPEAT n TIMES
{
    count <- count + 1
}
DISPLAY(count)

count = 0
for i in range(4):
    for j in range(4):
        count = count + 1
print(count)

Reasonable Time vs Unreasonable Time

The CED draws one big line. An algorithm runs in reasonable time when its step count grows like a polynomial in n: n, or n squared, or n cubed. These grow, but at a pace we can plan around. An algorithm runs in unreasonable time when its step count grows like an exponential, such as 2 to the n. Exponential growth starts small and then detonates.

Look at the numbers. For 2 to the n: at n = 10 it is about a thousand, at n = 20 about a million, at n = 40 about a trillion, at n = 60 it is more steps than a fast computer could finish in a lifetime. An exponential-time solution becomes infeasible almost immediately as the input grows, even though it may look harmless for tiny inputs. That is why "it works on my small test" is not proof that an algorithm is efficient.

# a brute-force search tries every subset
# of n items, so its steps grow like 2 ** n
# is that reasonable or unreasonable time?

When Exact Is Too Slow: Heuristics

Some problems have no known efficient (reasonable-time) exact solution. Finding the truly shortest route that visits many cities is a classic example: checking every possible order is exponential and hopeless past a few dozen cities. When an exact answer is out of reach, we use a heuristic: a rule of thumb that produces a good-enough answer quickly, without guaranteeing the best possible answer.

A delivery app that always drives to the nearest unvisited stop next is using a heuristic. The route it builds is usually close to optimal and it is computed in reasonable time, which is a trade every real system makes: give up a guarantee of perfection to get an answer you can actually use. On the exam, remember the definition: a heuristic gives an approximate, good-enough solution faster than an exact method, and it is what you reach for when an efficient exact algorithm is not known.

Key Vocabulary