Algorithm

Why do we need algorithms?

A data structure tells us how data is organized, but organization alone is not enough. Organizing books on a shelf does not find you a specific book by itself. You still need a method: start from one end, check each title, stop when you find a match.

That method, the actual procedure for using the data to solve a problem, is an algorithm.

Every step in an algorithm has to be something you could actually carry out, by hand or in code, without guessing what it means. "Sort the list somehow" is not a step. "Compare the first two elements and swap them if the first is larger" is.

Characteristics of an algorithm

A sequence of steps only counts as an algorithm if it satisfies all of the following. Miss even one and it stops being a reliable procedure.

• Input: zero or more inputs may be supplied. Some algorithms take no input at all (print "hello world" needs none), but most operate on data you give them.
• Output: it should produce at least one meaningful output. A procedure that runs and produces nothing checkable cannot be judged correct or incorrect.
• Definiteness: every step should be clear and unambiguous. Two people following the same algorithm by hand must arrive at the same result.
• Finiteness: the algorithm must terminate after a finite number of steps. It has to actually finish and hand you an answer, not keep running indefinitely.
• Effectiveness: each step should be executable using the basic operations available, in a finite amount of time.

Finiteness is why a search that "keeps looking forever if the item is not found" is a flawed algorithm. A proper search must also handle the case where the item is missing, report that, and stop.

Example: same problem, two algorithms

Problem: find the sum of all numbers from 1 to n.

1. Start with sum = 0.
2. Add each number from 1 to n one by one.
3. Return sum.

1. Use the formula: sum = n x (n + 1) / 2
2. Return sum.

Both algorithms are correct. Both satisfy all five characteristics above. But they are not equally good. Algorithm 1 does one addition per number, so for n = 1,000,000 it performs a million additions. Algorithm 2 always does one multiplication and one division, no matter how large n is.

The two algorithms differ in how their cost grows as the input grows, even though they compute the exact same answer. That growth in cost is what "efficiency" actually measures. For a small n the difference is barely noticeable, but for a large n it can mean the difference between milliseconds and minutes.

This is why the same problem can have many valid algorithms worth comparing, and why the next topic looks at how to measure and compare that cost systematically: performance analysis.