Module 05: Algorithms and efficiency

Choose input size and an operation before counting. For n constant-sized keys, linear search needs at most n equality checks. O(g(n)) is an asymptotic upper bound up to a constant after some threshold; Ω is a lower bound and Θ is both. A function 3n+7 is Θ(n), because constants and fixed terms do not change large-n growth. Saying O(n²) can be true but loose for that function. These are mathematical bounds, not timings or automatically worst-case claims: state which case you analyse.

Binary search requires sorted keys and efficient indexed access. Maintain a half-open interval [lo,hi), initially [0,n). Inspect mid=(lo+hi)//2. To find the first matching position, advance lo past mid if the key is smaller; otherwise move hi to mid, keeping possible equal keys on the left. When lo=hi, check the insertion position for equality. Each probe removes roughly half the candidates, giving O(log n) probes. Sorting an unsorted list before one query can cost more than a single linear scan.

Before iteration i, the prefix [0,i) is sorted and contains exactly the original prefix's items. Take item i as key, shift larger preceding items right, and insert the key into the gap. This preserves the invariant and reaches a sorted whole list. Using > rather than >= for shifts preserves equal-key order, making the sort stable. Already sorted input takes n−1 key comparisons; reverse input takes 1+…+(n−1)=n(n−1)/2. A copied-input implementation also allocates an n-entry output.

Merge sort splits, sorts halves and merges in linear work, giving Θ(n log n) comparisons in its usual worst-case analysis and O(n) merge storage. Quicksort partitions around a pivot: typical average work is Θ(n log n), but poor pivots can give Θ(n²). A comparison-based sorter distinguishing n! permutations needs Ω(log₂(n!))=Ω(n log n) comparisons in the worst case. Counting sort can beat this bound only by using restricted integer keys and extra structure, so it does not contradict the comparison-model bound.

Separate input storage, output storage and auxiliary working space. Iterative binary search needs O(1) auxiliary state, while a recursive version consumes O(log n) stack space. Best, worst and average cost refer to different input assumptions; an average needs a distribution. Benchmarks answer practical questions but must use equivalent outputs, comparable data and repeated runs. Operation counts reveal growth; timings reveal constants and environment. Neither replaces correctness checks.

Download each script and run it in a terminal with Python 3.11 or later: python m05_search.py. On Windows, py -3 is an alternative; on some systems use python3. The labs use only the standard library. Predict the result before running, then complete the variations. Run without -O so assertions remain enabled. Outputs below were captured by the builder. Code and output are identical in both language editions.

Trace lo and hi by hand before running. probes counts interval probes; the final equality check is separate.

Download m05_search.py

"""Binary search maintains a half-open candidate interval [lo, hi)."""
def binary_search(items, target):
    lo, hi, probes = 0, len(items), 0
    while lo < hi:
        mid = (lo + hi) // 2
        probes += 1
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    found = lo if lo < len(items) and items[lo] == target else -1
    return found, probes

for size in [0, 1, 8, 16, 32]:
    items = list(range(size))
    found, probes = binary_search(items, size)
    assert found == -1
    print(f"n={size:2}, absent insertion point={size:2}, probes={probes}")
assert binary_search([1, 2, 2, 4], 2)[0] == 1
assert binary_search([], 1) == (-1, 0)
print("duplicate case returns first match")

n= 0, absent insertion point= 0, probes=0
n= 1, absent insertion point= 1, probes=1
n= 8, absent insertion point= 8, probes=3
n=16, absent insertion point=16, probes=4
n=32, absent insertion point=32, probes=5
duplicate case returns first match

1. Search each value in a 16-entry list.
2. Try [2,1] and explain the violated assumption.
3. Change hi=mid to hi=mid−1 and find a missed boundary.

Check sorted output for empty, duplicate, sorted and reversed inputs.

Download m05_sort.py

"""Insertion sort counts key comparisons, not elapsed seconds."""
def insertion_sort(values):
    result = values.copy()
    comparisons = 0
    for i in range(1, len(result)):
        key, j = result[i], i - 1
        while j >= 0:
            comparisons += 1
            if result[j] <= key:
                break
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = key
    return result, comparisons

for values in [[], [1], [1, 2, 3, 4], [4, 3, 2, 1], [2, 1, 2]]:
    result, count = insertion_sort(values)
    assert result == sorted(values)
    print(values, "->", result, "comparisons:", count)

[] -> [] comparisons: 0
[1] -> [1] comparisons: 0
[1, 2, 3, 4] -> [1, 2, 3, 4] comparisons: 3
[4, 3, 2, 1] -> [1, 2, 3, 4] comparisons: 6
[2, 1, 2] -> [1, 2, 2] comparisons: 2

1. Run reversed lengths 8 and 16.
2. Track original positions of equal keys.
3. Explain the memory cost of values.copy().

Try before opening the solution. ★ applies an idea; ★★ combines ideas; ★★★ asks for design or proof.

Choose an answer for feedback; reset to retry. A text answer key is available without JavaScript.

• MIT algorithms course — Use the sorting and binary-search materials; identify a precondition in each algorithm.

Trace binary search on five items and justify every discarded interval. State insertion sort's invariant. Module 06 examines how the representation changes operation costs.