Computer ScienceThinking in Steps: Designing and Comparing Algorithms
Byte the friendly robot stands at a glowing whiteboard, marker in hand, arranging numbered step cards into a clear ordered sequence for finding a name in a long list — grinning as each card clicks into place.
- Define an algorithm as a precise, ordered sequence of unambiguous steps.
- Sequence the steps of an algorithm into the correct order to solve a simple everyday problem.
- Identify and fix an instruction that is ambiguous or out of order.
- Compare two algorithms that both work and explain which is more efficient and why.
Key terms
- Correctness
- An algorithm always gives the right answer for every valid input
- Efficiency
- How much work, in steps or time, an algorithm needs to finish
- Unambiguous step
- A step with only one possible meaning for any follower
- Halving search
- A strategy that discards half the remaining items at each step
Correct But Not Equal
Two algorithms can both be correct yet differ enormously in speed. Correctness only asks whether you reach the right answer; efficiency asks how much work that took. Checking every dictionary page and using the smart middle-and-halve method both find the word, so both are correct. The halving method just gets there in far fewer steps. This is why programmers rarely stop at 'it works' — a slow correct program can still be useless when the data is huge.
How Halving Beats Checking Each One
When a list is sorted, the middle-and-halve method throws away half the remaining items every single look, because the target can only live in the half on one side. Starting with one hundred names, you go to about fifty, then twenty-five, then thirteen, and so on. Each cut roughly halves what is left, so you reach a single candidate in around seven looks instead of one hundred. Checking names one by one cannot use the sorted order, so it has no shortcut.
Worked examples
Count steps to find a name in 8 sorted names
- Start with all 8 names; look at the middle one.
- The target is in one half, so discard the other half, leaving 4.
- Look at the middle of those 4; discard a half, leaving 2.
- Look at the middle of those 2; discard a half, leaving 1.
- That last name is checked, so 8 names took at most 4 looks.
Answer: At most 4 steps, because 8 halves to 4 to 2 to 1
Decide if a step is ambiguous
- Read the step: 'add a bit of flour.'
- Ask whether two people would do the exact same thing.
- One person adds a spoonful, another adds a cupful — different amounts.
- Different results mean the step has more than one meaning.
Answer: The step is ambiguous because 'a bit' has no exact amount
Activity
Algorithms work for any problem — including making lunch! Drag these steps into the correct order to make a working algorithm for a peanut-free jam sandwich.
Practice
Explain which is more efficient for 64 sorted items and why.
Rewrite the ambiguous step 'cook until done' to be unambiguous.
Common mistakes to avoid
- Checking every item is more correctBoth methods are correct; checking every item is just slower, not more accurate.
- Two correct algorithms take the same timeCorrect algorithms can still differ greatly in the number of steps they require.
Check your understanding
Which choice is the BEST description of an algorithm?
Algorithm A checks all 100 names one by one. Algorithm B uses the middle-and-halve method on the same sorted list. Both find the right name. Which is more efficient and why?
A friend writes this step in a recipe: "Add a bit of flour." Why is this a weak step in an algorithm?
Recap
An algorithm must be precise, ordered, and unambiguous so it is correct for every valid input. Efficiency compares how many steps two correct algorithms take, and a halving strategy on sorted data needs far fewer steps than checking each item.
Reflect
When is a slower but simpler algorithm still the better choice for you?