Comparing Algorithms

Correct Is Not the Same as Good

By now you can design an algorithm, and you have met pairs that do the same job differently: linear versus binary search, bubble versus merge sort. Both members of each pair are correct. They are nowhere near equal.

Judging between correct algorithms is a skill of its own — arguably the skill of computer science. The judging criteria are called efficiency: how much time and how much memory an algorithm needs.

Think in Growth, Not Stopwatches

Here is the beginner's trap: testing two algorithms on a small input, seeing both finish instantly, and concluding they are the same. On 10 items, everything is instant. The real question is: what happens as the input grows?

Count steps as the data scales:

Items (n)	Binary search (~log n)	Linear search (~n)	Compare-all-pairs (~n²)
100	7	100	~5,000
10,000	14	10,000	~50 million
1,000,000	20	1,000,000	~500 billion

Read down each column. Binary search barely notices a million items. Linear search grows in step with the data — double the items, double the work. And the pairs column explodes: squared growth turns a million items into a job of hundreds of billions of steps. Some perfectly correct algorithms are, in practice, unusable at scale.

This gives you a vocabulary for growth: constant (same work regardless of size), logarithmic (halving tricks, like binary search), linear (touch everything once), and squared (compare everything with everything). Recognising which family an algorithm belongs to is high-value pattern recognition.

Where Squared Growth Sneaks In

Nobody sets out to write a slow algorithm. Squared growth arrives innocently: a loop inside a loop, each running once per item. "For every student, check against every other student for duplicate names" — natural to write, fine for one class, hopeless for a national database. When you spot a nested loop over the same large data, an alarm should ring: is there a better way? (Often: sort first, or use a lookup structure — the standard escapes.)

Time Is Not the Only Cost

Algorithms also consume memory — working space. Merge sort is fast partly because it uses extra space for merging; bubble sort crawls but rearranges the list in place, needing almost no extra room. On a big server, memory is cheap and time is precious. On a tiny embedded device, memory may be the scarcer resource. Time versus space is a genuine trade-off, and the right choice depends on the machine and the job.

The Best Algorithm Depends on the Job

There is rarely one champion. The honest answer to "which is better?" is usually it depends — on the data and how it will be used:

• Searching once through unsorted data? Linear search — sorting first costs more than it saves.
• Searching the same data thousands of times? Sort it once, then binary search forever — the investment repays itself.
• Ten items? Do the simple thing. Simplicity is also a virtue: simple code is easier to debug and to trust.

Engineers weigh exactly these questions daily. The reasoning tool is always the same: count the steps, watch the growth, know your data.

Try It Yourself

You need to find whether two students in a school of 1,000 share a birthday. Plan A: compare every pair (~500,000 comparisons). Plan B: make 366 labelled boxes, drop each student's name into their birthday's box, and watch for a box with two names (~1,000 steps). Same answer, three orders of magnitude apart — and Plan B is a memory-for-time trade. Now find a Plan B for duplicate names.

Worked Example — Comparing Two Real Approaches to One Problem

Take a genuinely practical problem: given a list of 10,000 email addresses, find out whether any address appears twice. Compare two algorithms honestly, the way this lesson recommends — by counting steps as the input grows, not by guessing.

Plan A — compare every pair: for each email, check it against every other email in the list. With 10,000 emails, that's roughly 10,000 × 10,000 ÷ 2 ≈ 50 million comparisons — squared growth, exactly the pattern flagged earlier in this lesson as a warning sign.

Plan B — sort first, then scan once: sort the list (a well-chosen sort takes roughly 10,000 × log(10,000) ≈ 130,000 steps), then walk through the sorted list once, comparing only each item with its immediate neighbour — duplicates end up next to each other after sorting, so one linear pass (10,000 more steps) finds them all.

Plan A:  ~50,000,000 steps
Plan B:  ~130,000 (sort) + 10,000 (scan) ≈ 140,000 steps

Plan B does the same job in roughly 1/350th of the work, purely by choosing a smarter combination of already-known techniques — sorting plus a single scan — instead of the instinctive "check everything against everything" approach. This is precisely why comparing algorithms matters in real engineering: the correct answer was never in doubt for either plan, but only one of them would actually finish in reasonable time on a list of 10 million emails instead of 10,000.

Key Words

• Efficiency — how much time and memory an algorithm needs
• Growth rate — how the work scales as the input grows (constant, logarithmic, linear, squared…)
• Worst case — the most work the algorithm could possibly need
• Time–space trade-off — spending memory to save time, or vice versa
• Nested loop — a loop inside a loop; over the same data, a classic source of squared growth