Notebook 7: Algorithms, Complexity & the Limits of Computation

COMP 1150 — Computer Science Concepts

Author

Brendan Shea, PhD

Published

June 6, 2026

Open In Colab
Download .ipynb · View on GitHub

📺 Lecture video: (link coming soon)

Learning Outcomes

By the end of this notebook, you will be able to:

  • Perform a linear search over a list and explain when it is the only option.
  • Perform a binary search over a sorted list, and explain why the list must be sorted first.
  • Reason informally about running time using Big-O names — O(n), O(log n), O(n²), O(n log n) — to describe how work grows as data grows.
  • Hand-code one simple sorting algorithm (selection sort) and describe how a faster one (merge sort) works.
  • Use Python’s built-in sorted() and .sort() with a key= function to sort numbers, strings, and objects.
  • Describe a Turing machine as a thought experiment and say what it means for a problem to be computable.
  • Explain the halting problem and what it means for a problem to be undecidable.
  • Discuss P vs. NP as the cultural idea “easy to check, hard to solve,” and connect these limits to what modern AI / LLMs can and cannot do in principle.

Maps to course LOs: 4, 13

The Problem: The Queen Wants It Found, and Now

The Queen of Hearts keeps an enormous, hopelessly shuffled deck. Every card is a guest, a gardener, or a tart in her ledger. When she wants a particular Knave, she expects him produced instantly — and “Off with their heads!” is the penalty for being slow.

Alice has been handed the deck and told to make it findable. The White Rabbit, forever checking his pocket-watch and muttering “no time, no time!”, will be our guide to the question that haunts every search: how many steps did that take?

But by the end of this notebook a stranger question appears, whispered by the Cheshire Cat from his branch: are there tasks that no algorithm — and no computer, ever — can finish at all?

The Roadmap

This notebook comes in two halves.

Part 1 — Making things fast. We start with the two ways to find a card: checking every one (linear search) versus repeatedly cutting the deck in half (binary search). Binary search only works on a sorted deck, so we learn to sort. Along the way the White Rabbit teaches us to count steps with Big-O notation.

Part 2 — What can’t be made fast, or done at all. Some problems are merely slow (the Queen’s impossible puzzles — P vs. NP). Others can never be solved by any program, no matter how clever (the halting problem and undecidability). We close by asking what all this means for modern AI and large language models.

Part 1 — Searching, Sorting & How Long It Takes

Linear Search: Check Every Card

Alice’s deck is shuffled — no order at all. She is told to find the Knave of Hearts. With a random pile, she has no shortcut: she must turn over the top card, check it, and if it is not the Knave, move to the next. She keeps going until she finds him or runs out of cards.

That is a linear search: walk through the items one at a time, in order, comparing each to your target.

Understanding the Code

  • for index in range(len(items)) walks the positions 0, 1, 2, … in order.
  • if items[index] == target compares the card at that position to the one we want.
  • The moment we find a match we return index — we stop early, we do not keep looking.
  • If the loop finishes without ever matching, we fall through to return None. That None is our sentinel value: a special return that means “not found.” (As noted above, None is safer here than -1, which Python would accept as the last index.)

Notice the cost: if the Knave is near the bottom of the deck, Alice turns over nearly every card. If he is not in the deck at all, she turns over every single one.

🔮 Predict Before You Run

The deck has 12 guests. Before running the next cell, predict:

  1. If the target is the last guest, how many comparisons does linear_search make?
  2. If the target is not in the deck at all, how many comparisons does it make?
  3. On average, for a random target that is present, roughly how many?
deck12 = [f"Card {i}" for i in range(1, 13)]   # "Card 1" ... "Card 12"

def linear_search_counting(items, target):
    comparisons = 0
    for index in range(len(items)):
        comparisons += 1
        if items[index] == target:
            return index, comparisons
    return None, comparisons

print("last item:   ", linear_search_counting(deck12, "Card 12"))   # 12 comparisons
print("missing item:", linear_search_counting(deck12, "Card 99"))   # 12 comparisons
print("first item:  ", linear_search_counting(deck12, "Card 1"))    # 1 comparison

The pattern: worst case is n comparisons for a deck of n cards. Best case is 1 (lucky first card). On average, about n/2. The thing that matters most is that the work grows in step with the size of the deck — double the deck, double the worst-case work. Hold that thought; the White Rabbit will name it soon.

Binary Search: Cut the Deck in Half (Again and Again)

The White Rabbit is appalled at all this card-turning. “There’s a faster way!” he insists — but only if the deck is already sorted.

Think about how you find a word in a dictionary. You do not start at “aardvark” and read every word. You flip to the middle, see whether your word is earlier or later, and throw away the half it cannot be in. Then you repeat on what remains. Each look halves the search.

That is binary search, and it requires the data to be in order.

Understanding the Code

  • low and high mark the range still worth searching. Everything outside it has been ruled out.
  • mid = (low + high) // 2 picks the middle position (integer division throws away the remainder).
  • The three branches: equal → found; mid is too small → answer must be to the right, so low = mid + 1; mid is too big → answer is to the left, so high = mid - 1.
  • while low <= high keeps going until the range is empty. When low passes high, there is nothing left, so we return None.
  • The little report helper checks if result is None so the printout never says the contradictory “found at index None” — it says plainly that the card is not in the deck.

Run the printed steps again: each line throws away half of what remained. A deck of 1,000 cards is found in about 10 steps, not 1,000.

Picture It: Halving the Search Space

Binary search on 16 cards needs at most 4 steps, because 16 halves to 8, to 4, to 2, to 1. The diagram below shows that shrinking range.

A Trap: Binary Search on an Unsorted List

Binary search trusts that the deck is sorted. Give it a shuffled deck and it will happily rule out the wrong half — and report “not found” for a card that is sitting right there. It fails silently, which is the worst kind of failure.

shuffled = ["March Hare", "Dormouse", "Knave of Hearts",
            "Duchess", "Mad Hatter", "Gryphon"]   # NOT sorted

# The Knave IS in the list, but binary search may not find him:
result = binary_search(shuffled, "Knave of Hearts")
print("\nResult on the unsorted deck:", result, "(should have been found!)")
print("Lesson: always sort before you binary-search.")

Why Order Matters: Counting the Rabbit’s Steps

The White Rabbit does not care about seconds — those depend on whose computer you use. He cares about how the number of steps grows as the deck grows. Computer scientists write this with Big-O notation. You can read O(...) as “on the order of…”

The four you will meet most often, from wonderful to dreadful:

Big-O Name What it means Our example
O(1) constant same work no matter the size grabbing the top card
O(log n) logarithmic each step throws away a fraction binary search
O(n) linear work grows in step with size linear search
O(n log n) “n log n” a good sort’s cost merge sort, sorted()
O(n²) quadratic work grows with the square selection sort (next)

Big-O ignores constants and small terms. We do not say “3n + 7 steps”; we say O(n). The point is the shape of the growth, not the exact count.

import math

print(f"{'deck size n':>14} | {'linear O(n)':>12} | {'binary O(log n)':>16}")
print("-" * 48)
for n in [16, 1024, 1_000_000, 1_000_000_000]:
    linear = n                       # worst-case comparisons
    binary = math.ceil(math.log2(n)) # worst-case comparisons
    print(f"{n:>14,} | {linear:>12,} | {binary:>16,}")

Look at the bottom row. To find a card among a billion, linear search may check a billion; binary search checks about 30. That gap is the whole reason we bother to sort.

Picture It: How Work Grows

The same idea as a shape. As n grows, O(n²) shoots up, O(n) rises steadily, and O(log n) barely lifts off the floor.

✏️ Your Turn — Counting Steps, On Paper (no coding)

You have a sorted list of 16 guests. In the worst case:

  1. How many comparisons does linear search make?
  2. How many does binary search make? (Hint: how many times can you halve 16?)
  3. In two or three sentences, explain why binary search needs so many fewer — and what the deck must have that linear search did not require.

💭 Think About It — When Does Speed Actually Matter?

You’ve now counted how the work grows as the input gets bigger — linear search checks every card, binary search cuts the deck in half.

  • For a small list, linear and binary search both feel instant. At what scale does the difference start to actually matter? Think of real systems where the list is enormous.
  • A faster algorithm sometimes needs extra setup — binary search requires a sorted list. When is it worth paying that setup cost, and when would you just do the slow-but-simple thing?
  • Where in your own life have you felt the difference between something that scales well and something that grinds to a halt as it gets bigger — a line, a website, a group chat?

There are no single right answers here — share a sentence or two on each.

Sorting: Putting the Deck in Order

Binary search needed a sorted deck. So how does Alice sort one in the first place? There are many sorting algorithms; we will write one by hand and describe a faster one.

The hand-written one is selection sort, and its idea is exactly what it sounds like: find the smallest card and put it first; from what’s left, find the next smallest and put it second; repeat until the deck is in order.

The Syntax of a Selection Sort

The outer loop walks the position we are currently filling. The inner loop scans everything after it to find the smallest remaining card. Then one swap drops that card into place.

def selection_sort(items):
    for i in range(len(items)):
        smallest = i
        for j in range(i + 1, len(items)):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]   # swap into place
    return items
def selection_sort(items):
    """Sort items in place using selection sort, printing each pass."""
    for i in range(len(items)):
        smallest = i
        for j in range(i + 1, len(items)):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
        print(f"  after pass {i + 1}: {items}")
    return items


ranks = [7, 2, 10, 4, 1]
print("start:        ", ranks)
selection_sort(ranks)
print("sorted:       ", ranks)

Understanding the Code

  • The outer loop variable i is the slot being filled: first the position that should hold the smallest card, then the next, and so on.
  • smallest starts as a guess (i) and the inner loop updates it whenever it finds something smaller in the unsorted tail.
  • The line with two assignments at once is a swap: Python lets you write a, b = b, a to exchange two values without a temporary variable.
  • Watch the printed passes: after each one, the front of the list is sorted and growing.

The cost: for each of n slots, we scan the rest of the deck. That is roughly n × n work — O(n²). Fine for a handful of cards, painful for millions.

🔮 Predict Before You Run

Given the list [5, 3, 8, 1, 9], what will it look like after the first pass of selection sort (after the smallest card is placed in slot 0)? Write down your guess, then run the cell.

demo = [5, 3, 8, 1, 9]
selection_sort(demo)   # watch only the FIRST printed pass to check your prediction

✏️ Your Turn — The Hatter’s Selection Sort

The tea party seats guests by arrival time (smaller number = arrived earlier). Use selection sort to order the list, printing it after each pass so the Hatter can watch it tidy itself.

arrivals = [4, 1, 3, 2, 5]   # arrival times

def selection_sort(items):
    # TODO: selection sort, printing the list after each pass
    pass

selection_sort(arrivals)
print("seated in order:", arrivals)   # expected: [1, 2, 3, 4, 5]

A Faster Idea: Merge Sort (Described, Not Coded)

Selection sort is O(n²). For a deck of a million, that is a trillion comparisons. Real systems use smarter sorts that run in O(n log n) — and the classic example is merge sort. We will describe it rather than code it, because the idea matters more than the implementation here.

Merge sort uses divide and conquer:

  1. Divide. Split the deck into two halves. Split each half again. Keep splitting until every pile is a single card — and a single card is already “sorted.”
  2. Conquer (merge). Take two sorted piles and merge them into one sorted pile by repeatedly comparing the top card of each and taking the smaller. Merging two sorted piles is cheap and easy.
  3. Combine upward. Merge the small sorted piles into bigger sorted piles, and those into bigger ones, until the whole deck is one sorted pile.

Why is it faster? There are about log n levels of splitting (you can only halve n about log n times), and each level does O(n) work to merge everything — so the total is O(n log n). That is why sorted() can sort a million items in well under a second while selection sort would crawl.

Picture It: Divide and Merge

Merge sort splits all the way down, then merges back up.

The Practical Tool: sorted() and key=

In real programs nobody hand-writes selection sort. Python ships a fast O(n log n) sort built in. You meet it two ways: sorted(items) returns a brand-new sorted list, while items.sort() sorts the list in place. The real power comes from key=, which lets you sort by a computed value instead of the items themselves.

The Syntax of sorted() with a Key

sorted(items)                       # ascending order, returns a NEW list
sorted(items, reverse=True)         # descending order
items.sort()                        # sorts in place, returns None
sorted(items, key=some_function)    # sort by what some_function returns for each item

A key function receives one item and returns the value to sort by. A lambda is a tiny one-line function, handy here: lambda c: c.rank means “given a card c, sort by its rank.”

# Numbers and strings: the obvious cases
print(sorted([7, 2, 10, 4, 1]))                 # [1, 2, 4, 7, 10]
print(sorted(["Hatter", "Alice", "Duchess"]))   # alphabetical
print(sorted([7, 2, 10, 4, 1], reverse=True))   # [10, 7, 4, 2, 1]


# Sorting OBJECTS with key= (a Card class, picking up where Notebook 6 left off)
class Card:
    def __init__(self, name, rank):
        self.name = name
        self.rank = rank
    def __repr__(self):
        return f"{self.name}({self.rank})"

hand = [Card("Knave", 11), Card("Two", 2), Card("Queen", 12), Card("Seven", 7)]

print("\nby rank: ", sorted(hand, key=lambda c: c.rank))   # 2, 7, 11, 12
print("by name: ", sorted(hand, key=lambda c: c.name))     # alphabetical by name

Understanding the Code

  • sorted(...) hands back a new list and leaves the original untouched; .sort() rearranges the original and returns None (a common beginner bug: writing x = mylist.sort() and getting None).
  • reverse=True flips the order.
  • key=lambda c: c.rank tells sorted what to compare. Python calls that function on each card, gets back a rank number, and sorts by those numbers — without losing track of which whole card each number came from.
  • This is the everyday tool: you almost never implement a sort, but you constantly choose what to sort by.

Picture It: Which Method, When?

Tool Needs sorted input? Changes the list? Big-O Reach for it when…
Linear search no no O(n) data is unsorted or tiny
Binary search yes no O(log n) data is sorted and you search a lot
Selection sort no sorts in place O(n²) learning / very small lists
Merge sort no returns sorted O(n log n) you need a guaranteed-fast sort
sorted() / .sort() no new list / in place O(n log n) real code — almost always

✏️ Your Turn — Sorting the Knave’s Tarts with key=

The Knave has a list of Tart objects, each with a flavor (string) and a count (int). Use sorted(..., key=...) to produce two orderings: one by count (most tarts last), and one alphabetically by flavor. Use the built-in — don’t write your own sort.

class Tart:
    def __init__(self, flavor, count):
        self.flavor = flavor
        self.count = count
    def __repr__(self):
        return f"{self.flavor}x{self.count}"

tarts = [Tart("strawberry", 12), Tart("apple", 3), Tart("plum", 7)]

by_count  = None   # TODO: sorted(tarts, key=...) ascending by count
by_flavor = None   # TODO: sorted(tarts, key=...) alphabetically by flavor

print("by count: ", by_count)
print("by flavor:", by_flavor)

Part 2 — The Limits of Computation

So far, every problem has had a fast-enough answer: search smarter, sort first, count the steps. Now the Cheshire Cat fades into view, all grin, and asks a different kind of question. Not “how long will it take?” but: “Are there questions a machine can never answer at all — no matter how clever the algorithm, no matter how fast the computer?”

The astonishing answer, proved in 1936 by a mathematician named Alan Turing, is yes. This part is about ideas, not code. Read it like a set of philosophy puzzles.

A Machine Made of Almost Nothing: The Turing Machine

Before there were computers, Turing asked: what is the simplest possible device that could carry out any calculation a human follows by rote? His answer was a machine so simple it sounds like a toy:

  • An endless tape divided into squares (imagine the Caterpillar’s ribbon, unrolling forever).
  • A head that sits over one square and can read the symbol there, write a new symbol, and move one square left or right.
  • A tiny rulebook: “if you are in state A and you read a 1, write a 0, move right, and switch to state B.” A handful of such rules.

That is the whole machine. No screen, no memory chips — just a tape, a head, and a list of if-then rules.

Here is the shocking part. This ribbon-and-rulebook gadget can compute anything that your laptop, a supercomputer, or any future computer can compute. The claim that “anything computable can be computed by a Turing machine” is called the Church–Turing thesis. It is the reason we can talk about computation as a single universal idea, instead of a different idea for every brand of machine.

Picture It: The Tape, the Head, the Rulebook

# A tiny illustrative Turing machine: flip every bit on the tape, left to right.
def run_tiny_tm(tape):
    """Move right across the tape, flipping 1<->0, until we run off the end."""
    tape = list(tape)
    head = 0
    while head < len(tape):
        tape[head] = "0" if tape[head] == "1" else "1"   # write
        head += 1                                        # move right
    return "".join(tape)

print("before:", "110100")
print("after: ", run_tiny_tm("110100"))   # every bit flipped

💬 Discussion

  1. Why would anyone study such a slow, silly machine instead of a real computer? What do we gain by stripping computation down to a tape and a rulebook?
  2. The Church–Turing thesis says every computer is, deep down, “just” a Turing machine. Does that match your intuition about your phone? What would it mean if it were true?
  3. If a Turing machine can compute anything any computer can, what kind of question could possibly be off-limits to it? (We are about to find one.)

The Halting Problem: A Question No Program Can Answer

The White Rabbit is forever running. Alice wonders: will he ever stop, or run forever? For a program, this is a real and important question. Some programs finish (they halt); some get stuck in a loop and run forever. Wouldn’t it be wonderful to have a tool that, given any program and its input, always told you the truth: “this one halts” or “this one loops forever”?

Call that dream tool halts(program, input). Turing proved it cannot exist. Not “we haven’t built it yet” — it cannot exist, ever. Here is the idea, in plain English:

Suppose halts existed. Then we could build a mischievous program, call it Contrary, that does this: “Ask halts what I would do. If halts says I halt, then loop forever. If halts says I loop forever, then halt immediately.” Now run Contrary on itself. Whatever halts predicts, Contrary does the opposite — so halts is wrong. Since we built Contrary using only halts, the only escape is that halts never existed in the first place.

This is the same self-referential trick as “This sentence is false.” The halting problem is undecidable.

What “Undecidable” Really Means

Be careful: undecidable does not mean hard. A hard problem is one we can solve, just slowly. An undecidable problem is one for which no algorithm can ever give the right answer in every case — not with a faster chip, not with more memory, not with a cleverer programmer.

The halting problem is not a lonely exception. Many real questions reduce to it. “Will this program ever crash?” “Does this code contain a virus that will eventually trigger?” “Will these two programs always produce the same output?” In full generality, no program can answer these for all inputs. The best real tools (antivirus, type checkers, verifiers) settle for being usually right, or right on a restricted set of cases.

💬 Discussion

  1. In your own words, what is the difference between “impossible for now” and “impossible in principle”? Give a non-computing example of each.
  2. Imagine you are writing the autograder for this course, and you want it to detect any student program that has an infinite loop. Why does the halting problem mean you can never make that detector perfect? What could you do instead?
  3. The proof relies on a program asking about itself. Where else have you seen self-reference create a paradox?

P vs. NP: Easy to Check, Hard to Solve

Not every limit is about impossibility. Some problems are perfectly solvable but seem to require a hopeless amount of work. The Queen empties a sack of a thousand jigsaw pieces and roars, “Assemble it — perfectly — or off with your head!”

Notice two very different jobs:

  • Checking a finished puzzle is easy: glance at it, see that every piece fits. Quick.
  • Finding the solution from scratch may be brutal: in the worst case you try an astronomical number of arrangements.

Computer scientists capture this with two groups of problems:

  • P — problems we can solve quickly (in a reasonable, O(n^k)-ish number of steps). Searching and sorting live here.
  • NP — problems where we can check a proposed answer quickly, even if finding it might be slow. The jigsaw, scheduling 500 classes without conflicts, packing a truck optimally, solving a giant Sudoku.

The famous open question is: does P = NP? That is, if you can check an answer fast, can you always find one fast too? Almost everyone believes P ≠ NP (finding is genuinely harder than checking), but nobody has proved it. It is one of the seven Millennium Prize Problems — there is a literal $1,000,000 waiting for a proof either way.

💬 Discussion

  1. Describe an everyday task that is hard to do but easy to check that it was done right. Why does that gap feel familiar?
  2. Much of modern encryption relies on a problem being hard to solve but easy to check. If someone proved P = NP tomorrow with a practical method, why might a lot of internet security suddenly break?
  3. “Hard for any computer” (P vs. NP) and “impossible for any computer” (the halting problem) sound similar but are not the same. In your own words, what is the difference?

What This Means for AI and LLMs

It is tempting to think a powerful enough AI will eventually solve everything. The limits in this notebook say otherwise — and the distinction is worth getting right.

  • An LLM is still computation. A large language model runs on ordinary computers, so it cannot escape undecidability. There is no AI, however large, that can correctly decide whether any program halts. That limit is mathematical, not a matter of training data or model size.
  • Some limits are about impossibility; others are about cost. P vs. NP–style problems are allowed to have solutions — they are just expensive. An AI might find good approximate answers fast (and often does), but “found a decent schedule” is not the same as “proved this is the best possible one.”
  • Be precise about what LLMs are bad at. It is easy to blur two very different things:
    • Impossible in principle — e.g., a perfect universal halting-detector. No program, AI or not, can do this.
    • Hard or unreliable in practice — e.g., guaranteeing a proof is correct, never hallucinating a fact, or producing a genuinely optimal solution. These are real weaknesses, but they are engineering and reliability problems, not mathematical impossibilities.

The healthy stance is neither hype nor despair: AI is a remarkable tool within the space of computable, tractable problems, and the theory tells us exactly where the hard walls are.

💬 Discussion

  1. A headline claims, “AI will soon solve any problem we throw at it.” Using the halting problem and P vs. NP, write a careful one-paragraph response.
  2. What is the difference between a task an LLM is merely bad at and a task that is mathematically impossible for any program? Give one example of each.
  3. Where, in your own use of AI tools, should you stay skeptical of the assumption that “the AI will just figure it out”?

💬 Discussion — The Cheshire Cat’s Riddle

The Cheshire Cat grins: “Some of my riddles are merely slow to answer. One of them can never be answered at all.”

In your own words, and with an everyday analogy of your choosing, explain the difference between:

  • a problem that is undecidable (like the halting problem), and
  • a problem that is merely hard (an NP problem like the giant jigsaw).

Then name one place this distinction should change how much we trust an AI system. There’s no single right answer — share your analogy and reasoning, and respond to a classmate whose analogy differs from yours.

✏️ Capstone — The Great Wonderland Race (AI-Assisted)

Time to put the last two notebooks into one small game. You’ll build a race: several characters, each with their own stats, run against each other; you bet on a winner; then the results are shown as a leaderboard, sorted fastest to slowest. It reviews objects (Notebook 6 — each racer is an object with attributes) and the star skill of this notebook (sorted() with key=, to rank the finishers).

The default is a Wonderland race — the White Rabbit, the Mad Hatter, the Cheshire Cat — but pick your own: horses, robots, snails, your friends as superheroes, anything that can race.

How the game works, start to finish:

  1. Each racer is an object with a few stats — say speed, stamina, and a dash of luck.
  2. Each racer’s finish time is computed from those stats — give faster racers an edge, but let luck shake things up so the same one doesn’t always win.
  3. The player bets on a racer by name.
  4. The finishers are sorted by time with sorted(..., key=...) and printed as a leaderboard.
  5. The game says whether the bet paid off.

Step 1 — Design it first (before the AI). In a markdown cell, jot down: your theme, your 3–5 racers and their stats, how a racer’s finish time is computed from its stats, and how the bet wins or loses.

Step 2 — Turn your design into a prompt. Fill the blanks and send it to Gemini (or Claude / ChatGPT):

Write a small race game in Python for Google Colab. Theme: [your theme]. Define a Racer class with a name and these stats: [your stats]. Create a list of [number] racers. Give each racer a method that computes its finish time from its stats plus a little randomness. Ask the player to bet on one racer by name. Run the race, then use sorted(..., key=...) to print a leaderboard from first place to last, and say whether the bet won. Keep it short and beginner-readable, with a comment on each part.

Step 3 — Get the bones working, then test. Paste it into the cell below and run it now. Get the simplest version working first — two racers, a finish time each, sorted into an order — and check the leaderboard by hand before adding more.

Step 4 — Add the bells and whistles. Once a basic race runs, add one or two, testing after each: a luck stat that can upset the favourite, different racer types via a subclass (a Sprinter that starts fast, a Stayer with high stamina — that’s inheritance from Notebook 6), payout odds on the bet, or a best-of-three series.

Step 5 — Check your work. Run it a few times. Does the leaderboard always come out in the right order (the slowest time should be last)? Try an empty racer list, or a bet on a name that isn’t running — does the game cope, or crash?

Step 6 — Reflect. In a markdown cell, write 2–3 sentences: which Notebook 6 idea (an object? a method? inheritance?) made the racers easy to build, and where did sorted(key=...) save you from writing a sort by hand?

Remember the course rule: AI is a fast first draft. You verify.

# ✏️ Paste your AI-built race game here, then run it and fix what's broken.

Key Terms

  • Algorithm — a step-by-step procedure for solving a problem.
  • Linear search — checking items one by one; O(n).
  • Binary search — repeatedly halving a sorted list; O(log n).
  • Sentinel value — a special return (we use None) meaning “not found.” Avoid -1 in Python, since it is a valid (negative) index.
  • Big-O notation — a description of how an algorithm’s work grows with input size.
  • O(1), O(log n), O(n), O(n log n), O(n²) — constant, logarithmic, linear, “n log n,” and quadratic growth.
  • Selection sort — a simple O(n²) sort: repeatedly select the smallest remaining item.
  • Merge sort — a fast O(n log n) divide-and-conquer sort.
  • Swap — exchanging two values, e.g. a, b = b, a.
  • In-place — rearranging a list without making a new one.
  • Key function — a function passed to sorted(..., key=...) that returns the value to sort by.
  • Turing machine — a minimal tape-and-rulebook model of computation.
  • Church–Turing thesis — the idea that anything computable can be computed by a Turing machine.
  • Computable — solvable by some algorithm.
  • Halting problem — deciding whether an arbitrary program halts; proven impossible.
  • Undecidable — no algorithm can solve every case, even in principle.
  • P — problems solvable quickly.
  • NP — problems whose answers can be checked quickly.
  • P vs. NP — the open question of whether fast-to-check implies fast-to-solve.
  • Intractable — solvable in principle but requiring impractically much work.

Summary

Part 1 — speed. Finding something is slow if you check everything (linear search, O(n)) and fast if the data is sorted and you halve it each step (binary search, O(log n)). Sorting is what makes that speed possible: we hand-coded selection sort (O(n²)) and described the faster merge sort (O(n log n)), then met the real-world tool, sorted() with key=. Big-O lets us compare strategies by how their work grows.

Part 2 — limits. Some problems are merely expensive: NP problems are easy to check but seem hard to solve, and whether P = NP is a famous open question. Other problems are impossible for any program: the halting problem is undecidable, a wall no computer — and no AI — can ever cross. Knowing the difference between “slow,” “intractable,” and “impossible” is part of thinking clearly about what computers, and AI, can really do.

What’s Next

Notebook 8 — Software Engineering: SDLC, Git & AI-Assisted Development. How real software gets built: the development lifecycle, Waterfall vs. Agile, using Git and GitHub from Colab, AI-assisted workflows (spec → code → test → review), and the basics of testing.