Unit 9 · Intro to Programming

Searching, Sorting & Complexity

The first properly computer-science unit. Two algorithms that do the same job can differ by a factor of a million on real data, and the difference is visible from the shape of the loops without running anything. Learning to see it is the point.

By the end you can

Implement linear and binary search and state what each requires.
Explain why binary search takes about $\log_2 n$ steps.
Read the big-O of a function from its loop structure.
Say why $O(n^2)$ sorting is unusable at scale.

Why it matters & where it comes from

Why it exists

Hardware gets faster by constant factors; algorithms improve by growth rates. A better growth rate beats a faster machine at every size past some threshold, and the threshold is usually small.

In the real world

A database index turns a linear scan into a logarithmic lookup, which is why queries return instantly instead of after a minute. Every autocomplete, every route search, every recommendation is a growth-rate decision made by someone.

Story & open questions

Binary search was described in 1946 but the first correct published implementation for arbitrary list lengths took until 1962 — the boundary conditions are genuinely hard. A midpoint overflow bug survived in Java's standard library until 2006.

Linear search

Example Look at everything

python

def linear_search(xs: list, target) -> int:
    """Return the index of target in xs, or -1 if it is absent.

    >>> linear_search([4, 9, 2], 9)
    1
    >>> linear_search([4, 9, 2], 7)
    -1
    """
    for i in range(len(xs)):
        if xs[i] == target:
            return i
    return -1

Works on any list, sorted or not. That generality is its whole advantage.

Best case one comparison, worst case $n$. On average about $n/2$, which still grows in proportion to $n$ — so we call it $O(n)$.

Binary search

Rule Requires a sorted list

Binary search compares against the middle item and discards half the list each time. Discarding is only justified if the list is sorted — on unsorted data it returns wrong answers silently, which is worse than failing.

Example Halve it each round

python

def binary_search(xs: list, target) -> int:
    """Return an index of target in sorted xs, or -1 if it is absent.

    >>> binary_search([2, 4, 9], 9)
    2
    >>> binary_search([2, 4, 9], 5)
    -1
    """
    lo = 0
    hi = len(xs) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if xs[mid] == target:
            return mid
        elif xs[mid] < target:
            lo = mid + 1      # target is in the upper half
        else:
            hi = mid - 1      # target is in the lower half
    return -1

The + 1 and - 1 matter. Without them the range never shrinks in some cases and the loop hangs.

lo <= hi not <: when they are equal there is still one unexamined item.

Rule Why it is $\log_2 n$

Each round halves the remaining range: $n$, $n/2$, $n/4$, and so on. The number of halvings before one item remains is the number of times $n$ can be divided by two, which is $\log_2 n$.

$n = 1{,}000$ needs about $10$ comparisons.

$n = 1{,}000{,}000$ needs about $20$.

A thousand times more data costs ten more steps. That is what a logarithm buys.

Big-O

Definition

Big-O names how the work grows as the input grows, ignoring constants and lower-order terms. It answers "what happens when the data gets ten times bigger?", not "how many seconds does this take?"

Example Reading it off the loops

python

xs[0]                          # O(1)     - one step regardless of size

for x in xs: ...               # O(n)     - one pass

for x in xs:                   # O(n^2)   - nested passes multiply
    for y in xs: ...

while lo <= hi: ...            # O(log n) - the range halves

xs.sort()                      # O(n log n) - Python's built-in sort

Sequential loops add, so two separate passes are still $O(n)$ — constants are dropped.

Nested loops multiply. That is the whole difference.

Rule The growth rates in this course

$O(1)$ — indexing a list, a dictionary lookup, a set membership test.

$O(\log n)$ — binary search.

$O(n)$ — linear search, summing, one pass.

$O(n\log n)$ — a good sort. This is the practical ceiling for comparison sorting.

$O(n^2)$ — nested loops over the same data, including x in some_list inside a loop.

Example What the difference costs

At $n = 100{,}000$, assuming a million basic operations per second:

$O(n)$: about $0.1$ seconds.

$O(n\log n)$: about $1.7$ seconds.

$O(n^2)$: about $10{,}000$ seconds, which is nearly three hours.

This is why Unit 6 kept recommending a set. Replacing x in a_list with x in a_set inside a loop turns the second row into the first.

Sorting

Example Selection sort, and why it is slow

python

def selection_sort(xs: list) -> None:
    """Sort xs in place into non-decreasing order."""
    for i in range(len(xs)):
        smallest = i
        for j in range(i + 1, len(xs)):
            if xs[j] < xs[smallest]:
                smallest = j
        xs[i], xs[smallest] = xs[smallest], xs[i]

The outer loop runs $n$ times and the inner runs up to $n$ times, so the total is proportional to $n^2$.

Worth writing once to understand, never worth using. Python's built-in sort is $O(n\log n)$ and implemented in C.

Rule Use the built-ins

xs.sort() sorts in place and returns None.

sorted(xs) returns a new sorted list.

sorted(xs, key=len) sorts by a computed value; reverse=True flips the order.

Sorting first to enable binary search costs $O(n\log n)$, which only pays off if you search many times. For a single lookup, a linear scan is faster.

Common pitfalls

• Binary search on an unsorted list. It returns wrong answers rather than erroring.
• Getting the midpoint update wrong and hanging. The range must strictly shrink every round.
• Writing O(2n) or O(n + 5). Constants are dropped; both are $O(n)$.
• Missing hidden loops. x in a_list is $O(n)$, so putting it inside a loop is $O(n^2)$ even though only one loop is visible.

Practice

Predict each answer before running it. Original exercises written for this guide in the style of the course's weekly sets.

Practice 1 · Count the comparisons

How many comparisons does binary search need on a sorted list of $1{,}000{,}000$?

Answer

About $20$, since $2^{20}$ is just over a million.

Practice 2 · Read the order

What is the big-O?

python

for x in xs:
    for y in ys:
        print(x, y)

Answer

$O(nm)$ where $n$ and $m$ are the two lengths. If both are the same list, $O(n^2)$.

Practice 3 · Hidden cost

What is the complexity of this?

python

out = []
for x in xs:
    if x not in out:
        out.append(x)

Answer

$O(n^2)$. The not in scans out, which grows, so the visible single loop hides a second one. Using a set makes it $O(n)$.

Practice 4 · Sequential loops

Two separate loops over the same list — what order?

Answer

$O(n)$. Sequential work adds, and constant factors are dropped.

Practice 5 · Off by one

What breaks if lo = mid replaces lo = mid + 1?

Answer

When hi = lo + 1, mid equals lo and the range stops shrinking, so the loop never ends.

Practice 6 · Sort with a key

Sort words by length, longest first.

Solution

sorted(words, key=len, reverse=True). Ties keep their original relative order, since Python's sort is stable.

Practice 7 · Sort then search?

Is it worth sorting a list to binary search it once?

Answer

No. Sorting is $O(n\log n)$ and a linear scan is $O(n)$, so a single lookup is cheaper unsorted. Sorting pays when you will search many times.

Practice 8 · Two sorted lists

Find values common to two sorted lists efficiently.

Solution

Walk both with two indices, advancing whichever points at the smaller value — $O(n + m)$. Alternatively set(a) & set(b), also linear and much shorter, at the cost of building the sets.

Expanded topic checklist

Course coverage. This unit is part of the complete CSC108H1 topic map. It should cover the following items before you move on:

Linear search. Implementation and $O(n)$ cost.
Binary search. Implementation, the sorted requirement, the boundary conditions, and $O(\log n)$.
Big-O. Reading growth from loop structure, dropping constants, spotting hidden loops.
Sorting. Why $O(n^2)$ sorts are unusable and what the built-ins provide.

Textbook/source alignment

The calendar names "searching, sorting, and complexity" explicitly. This is the most theoretical unit of the course and the one that carries most directly into CSC148H1.

Core idea map

Cost grows with input. Sequential work adds; nested work multiplies; halving gives a logarithm. Everything else is applying those three facts.

Study routine. For every function you write, name its big-O before moving on. It takes ten seconds and it is the habit CSC148H1 assumes you already have.

Deep practice extensions

Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.

Extension 1 · Precondition

What does binary search require?

Guide

A sorted list. On unsorted input it gives wrong answers without any error.

Extension 2 · Why logarithmic

Why $\log_2 n$ steps?

Guide

Each comparison halves the remaining range, and $\log_2 n$ is how many halvings reduce $n$ to one.

Extension 3 · Nested versus sequential

How do loop structures combine?

Guide

Sequential loops add and collapse to the largest term; nested loops multiply.

Extension 4 · Hidden linear work

Which common operations are secretly $O(n)$?

Guide

x in a_list, list.remove, list.insert(0, x), and string concatenation in a loop. Each turns an enclosing loop quadratic.

← Unit 08Unit testing & design Unit 10 →Floating point