AmouAI Hub/Courses/Programming Fundamentals/Day 11
Algorithm Design & Analysis
Derive binary search rather than memorise it, implement three sorts by hand, and get an honest feel for what Big-O is actually telling you.
By the end of today you can
- Derive binary search from the question "what can I throw away?"
- Say precisely what binary search requires, and what happens when it is missing
- Implement bubble, selection and insertion sort, and trace each by hand
- Count comparisons and swaps rather than guessing at speed
- Read Big-O as a statement about growth, not about time
- Explain why constants and small inputs are missing from the notation on purpose
- Recognise the accidental O(n²) that comes from a loop inside a loop
- Pick the right structure for a job using cost, not habit
▶Today's videos
Watch each video, then work the matching sections below. Watching alone will not do it.
in · picking a structure on cost rather than habit.1Search strategies
Two ways to find something, and an enormous gap between them.
Finding a value in a list one item at a time is the obvious approach, and it is the right one when you know nothing about the order. Watch how much work it does:
Nine comparisons for the second-to-last item. Now the same list, using the one fact we have been ignoring: it is sorted.
Deriving it, rather than memorising it
The whole algorithm falls out of one question: what can I throw away?
- Look at the middle item. It is either the answer, too small, or too big.
- If it is too small, everything at or left of it is too small. Discard that half.
- If it is too big, discard the other half.
- Repeat on what is left. Stop when you find it, or when nothing is left.
def binary_search(values, target):
"""Index of target in a SORTED list, or -1."""
low = 0
high = len(values) - 1
while low <= high:
mid = (low + high) // 2
if values[mid] == target:
return mid
if values[mid] < target:
low = mid + 1 # discard the left half
else:
high = mid - 1 # discard the right half
return -1
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 72))
print(binary_search(data, 4))while low < high instead of <= misses single-element ranges. low = mid instead of mid + 1 loops forever. And it silently gives wrong answers on unsorted input — no crash, no warning, just a -1 for a value that is right there. Test all three.
| Items | Linear (worst case) | Binary (worst case) |
|---|---|---|
| 10 | 10 | 4 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
A billion items, thirty comparisons. That is not a small optimisation — it is a different category of program. And the price is that the data must be sorted, which is what section 2 is about.
2Sorting, traced by hand
Three algorithms you will never ship, and should absolutely write once.
Python has sorted(), and you should use it. Writing these three yourself is not about the result — it is about being able to reason about cost, which is the actual skill.
Every pass drags the largest remaining value to the right. Simple to write, and it does an enormous amount of work — notice how many comparisons happen after the list is already sorted.
The same number of comparisons as bubble sort, but far fewer swaps: it only moves an item when it has finished deciding where it goes.
On already-sorted or nearly-sorted data it does almost no work — one comparison per item and no shifting. That is why real sorting implementations, including Python's Timsort, fall back to insertion sort for small or nearly-ordered runs. "Slow algorithm" is always a claim about a particular input.
def insertion_sort(values):
"""Sort a copy of values, ascending."""
items = values[:] # do not mutate the caller's list
for i in range(1, len(items)):
key = items[i]
j = i - 1
while j >= 0 and items[j] > key:
items[j + 1] = items[j] # shift right
j -= 1
items[j + 1] = key
return items
print(insertion_sort([5, 2, 9, 1, 7, 3]))Note line 3. Yesterday's aliasing lesson applies: without the [:] this function would reorder the caller's list as a side effect, which is exactly the kind of surprise Day 7 warned about.
3Growth, not notation
Big-O answers one question, and it is not "how fast is it?"
"If I double the input, what happens to the work?" That is all. Not seconds, not benchmarks, not whether your laptop is fast — how the cost grows.
| Complexity | Double the input and… | Example |
|---|---|---|
| O(1) | nothing changes | d[key], xs[3], xs.append(x) |
| O(log n) | one more step | binary search |
| O(n) | twice the work | x in a_list, sum(xs), one loop |
| O(n log n) | slightly more than double | sorted(), merge sort |
| O(n²) | four times the work | a loop inside a loop over the same data |
Why the constants are missing on purpose
An O(n) algorithm that does 100 operations per item is slower than an O(n²) one at n = 10. Big-O does not care, and that is a deliberate choice: constants depend on your machine, your language and this year's compiler. Growth does not.
"O(n log n) beats O(n²)" is a statement about large n. If your list always has eight items, pick whichever is clearest to read. Choosing a complicated algorithm for data that will never be big is a real and common mistake.
The accidental O(n²)
You will almost never sit down to design an algorithm. What you will do, constantly, is notice that a piece of code has a loop inside a loop — and know that this matters. Recognising accidental O(n²) is the single most valuable thing on this page.
>_Python playground
A real Python interpreter running inside your browser. Nothing is installed, nothing is uploaded, nothing can break.
input(), comma separated →
✓Exercise set
Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.
Day 12 — Classes & Objects
The problem OOP actually solves, shown by watching a dict-of-data mess become a class.