Comparing Solutions · Programming Concepts

Why it matters

The search strategies lesson showed two correct ways to find a value, with very different costs as the list grows. That’s not a special case — many problems have more than one correct solution, and picking between them means comparing more than “does it work.” Growth rate, readability, and correctness all matter, and none of them alone tells the whole story.

Mental model

Two solutions to the same problem — does a list contain any duplicate values?

PythonTwo correct solutions, very different loop structures

def has_duplicates_slow(numbers):
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            if i != j and numbers[i] == numbers[j]:
                return True
    return False


def has_duplicates_fast(numbers):
    seen = set()
    for number in numbers:
        if number in seen:
            return True
        seen.add(number)
    return False

Both are correct. has_duplicates_slow compares every item against every other item — a loop nested inside a loop. has_duplicates_fast makes one pass, checking membership in a set each time (see the sets and uniqueness lesson for why that check stays fast). The difference is their growth rate: how the amount of work scales as the list gets longer.

Trace it

Counting how many comparisons each makes on a list with no duplicates, at two different sizes:

Doubling the input: quadratic vs. linear growth
List size	has_duplicates_slow comparisons	has_duplicates_fast comparisons
4 items	16	4
8 items (doubled)	64 (4x as many)	8 (2x as many)

Doubling the input roughly quadruples the slow version’s work — a nested loop over the whole list, for every item in the list, is quadratic. The fast version’s work roughly doubles — a single pass over the list is linear. That gap only grows as the list gets longer; at 1,000 items the difference is far more dramatic than at 8.

Check your understanding

Or reveal the answer without checking

Answer:Linear — one loop over the input
A single loop that visits each item once, without any loop nested inside it, is linear: doubling the input roughly doubles the work in the worst case.

Or reveal the answer without checking

Answer:Correctness and readability matter too; a slower solution that's clearly correct and easy to follow can be the better choice for a small or infrequent task
Comparing solutions means weighing correctness, readability, and rough cost together — not defaulting to whichever runs fastest, especially when the input will always stay small.

Practice: warm-up

Classify each function’s growth rate — constant, linear, or quadratic — by looking at its loop structure.

def first_item(items):
    return items[0]

def total(items):
    result = 0
    for item in items:
        result = result + item
    return result

def all_pairs(items):
    pairs = []
    for a in items:
        for b in items:
            pairs.append((a, b))
    return pairs

Stuck? Reveal one hint at a time.

Hint 1
Count the loops: no loop at all, one loop, or a loop nested inside another loop.
Hint 2
all_pairs builds every combination of two items — how many pairs exist for a list of length n?

Reveal the classification

Try the problem yourself before reading this. There is often more than one reasonable approach — treat this as one worked example, not the only correct answer.

first_item -> constant (no loop; items[0] takes the same effort regardless of length)
total       -> linear (one loop, once over every item)
all_pairs   -> quadratic (a loop nested inside a loop, both over items)

Practice: apply it

A report-generation script uses has_duplicates_slow on a list that used to have a few dozen entries — but now has 50,000, and the report takes minutes to generate.

Or reveal the answer without checking

Answer:has_duplicates_slow is quadratic, so growing the input by a large factor grows the work by roughly the square of that factor
Quadratic growth means the cost scales with the square of the input size — a list that grew by roughly 1000x in length grows the work by roughly 1000x squared, which is dramatic.

Modification challenge: replace has_duplicates_slow with has_duplicates_fast in the report script, and explain in one sentence why that specific change addresses this problem.

Summary

More than one correct solution often exists for the same problem, and they can have very different growth rates.
A single loop over the input is linear; a loop nested inside another loop over the same input is quadratic — and the gap between them grows as input size grows.
Compare solutions on correctness first, then readability, then rough cost — not cost alone.
A slower solution isn’t automatically wrong; for small or infrequent inputs, the more readable choice can be the better one.

Key terms

Growth rate