1 · What an algorithm is & counting its steps
What makes something an algorithm, and how to count the steps it takes.
In one sentence
An algorithm is a precise, finite recipe that turns an input into an output. We judge it by counting how many basic steps it takes as the input size grows, written .
Everyday analogy
A recipe. A good recipe:
- lists its ingredients (input) and tells you what dish you'll get (output);
- has steps that are clear ("add 5 g salt", not "add some salt"): definiteness;
- ends at some point, not "stir forever": finiteness;
- only asks for things a cook can actually do: effectiveness.
Two cooks with different stoves (Java vs. C, fast vs. slow laptop) follow the same recipe. That's why we analyse the recipe itself, not one cook's stopwatch time.
Key ideas
| Idea | Meaning |
|---|---|
| 5 properties | input, output, definiteness, finiteness, effectiveness |
| Input size | how "big" the input is (array length, number of digits, …) |
| number of basic steps on an input of size | |
| Cost × frequency | total time = Σ (cost of a line × how many times it runs) |
| Best / worst / average case | fewest / most / typical steps over all inputs of size |
| Why not just time it? | stopwatch results depend on machine, language and the inputs you happened to try |
Pseudocode conventions used in this course: ← means assignment, = means equality test,
arrays start at index 1 (A[1..n]), and loops are written for i ← 1 to n do.
Counting steps for CountNegatives (our own example)
CountNegatives(A, n)
1 count ← 0
2 for i ← 1 to n do
3 if A[i] < 0 then
4 count ← count + 1
5 return count| Line | Cost | Times it runs | Why |
|---|---|---|---|
| 1 | 1 | once at the start | |
| 2 | successful checks + 1 failing check that ends the loop | ||
| 3 | once per element | ||
| 4 | between and | depends on how many negatives | |
| 5 | 1 |
- Best case (no negatives): , which is linear.
- Worst case (all negative): , still linear.
The pipeline from problem to program
Common mistakes
- Counting a loop header as instead of .
- Saying "best case = small input". Best/worst case are about inputs of the same size .
- Treating a library call like string concatenation or
copy()as one step. It can cost itself.
Mastery check
Solve without hints, then explain
For FindFirstZero(A, n), which scans left to right and stops at the first 0:
(a) Write its pseudocode. (b) How many comparisons does it make in the best and worst case? (c) Give an input that causes each.
(a) for i ← 1 to n do if A[i] = 0 then return i and, after the loop, return NIL.
(b) Best: 1 comparison (zero at position 1). Worst: comparisons (zero at the end or no zero at all).
(c) Best [0, 5, 7]; worst [5, 7, 0] or [5, 7, 9].
Status
Tick all six steps to unlock “Mastered”.
Which study mode worked for you?
References
- 01-02 Introduction: Slides 9–11 (the 5 criteria, language independence), 27–29 (problem-solving pipeline), 30 (design techniques).
- 03 Algorithm Analysis: Slides 9–14 (experimental vs. theoretical analysis), 15–18 (cost × frequency).
- 04 Correctness & Space: Slides 3–5 (pseudocode notation).
- CLRS 4e Ch 1 (role of algorithms), §2.2 (analysing algorithms).