B2.4 Programming Algorithms

B2.4.1: Big O Notation

Big O notation describes how the number of operations (time) or memory (space) an algorithm needs grows as the input size n grows. It gives the upper bound, so it describes the worst case. It measures scalability, not actual seconds.

Why it matters

Fastest to slowest: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Working out Big O

1. Find the operation that repeats most (usually inside the loops).
2. Count how many times it runs in terms of n.
3. Keep only the biggest term, drop constants. 3n + 5 → O(n). n² + n → O(n²).

def percent(x, y):          # O(1): 2 operations, whatever the input
    return x / y * 100

def find_max(values):       # O(n): the loop body runs n times
    highest = values[0]
    for v in values:
        if v > highest:
            highest = v
    return highest

def has_duplicate(values):  # O(n²): n passes of the inner loop for each of n outer passes
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return True
    return False

Time complexity = how the number of operations grows. Space complexity = how much extra memory is needed. Sorting in place (swapping inside the same list) is O(1) space.

B2.4.2: Linear and Binary Search

Linear search

Check every element in turn from index 0 until the target is found or the list ends. Works on unsorted data.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i          # found: return the index
    return -1                 # not found

playlist = ["The Old Bridge", "Down by the Fountain", "Super Searchin'",
            "Little Red Lies", "Geescht", "Watching Over You"]
print(linear_search(playlist, "Little Red Lies"))   # 3
print(linear_search(playlist, "Yesterday"))         # -1

Best case O(1) (first item). Worst case O(n) (last item or not there).

Binary search

Data must be sorted. Look at the middle element. If it is the target, stop. If the target is bigger, discard the left half; if smaller, discard the right half. Repeat on what is left.

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1         # target is in the right half
        else:
            high = mid - 1        # target is in the left half
    return -1

nums = [10, 11, 12, 15, 20, 25, 45, 84, 129, 139, 483, 586, 685]
print(binary_search(nums, 139))   # 9

Trace: searching for 139

Trace: searching for 13 (not in the list)

Each comparison halves the data, so worst case is O(log n). A million items need at most about 20 comparisons.

B2.4.3: Bubble Sort and Selection Sort

Bubble sort

Compare each adjacent pair and swap if they are in the wrong order. After each pass the largest unsorted value has "bubbled" to the end, so each pass checks one fewer element.

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):              # n - 1 passes
        swapped = False
        for j in range(n - 1 - i):      # last i items are already sorted
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:                 # no swaps: already sorted, stop early
            break
    return a

print(bubble_sort([10, 8, 349, 3, 39, 1]))   # [1, 3, 8, 10, 39, 349]

Trace (state at the end of each pass, green = in its final place):

Pass 1 in detail: 10>8 swap, 10<349 no swap, 349>3 swap, 349>39 swap, 349>1 swap.

Selection sort

Find the smallest value in the unsorted part and swap it into the first unsorted position. The sorted part grows from the left by one each pass.

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):       # find the smallest in the unsorted part
            if a[j] < a[min_index]:
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]   # one swap per pass
    return a

print(selection_sort([10, 8, 349, 3, 39, 1]))   # [1, 3, 8, 10, 39, 349]

Selection sort can also find the largest each pass and place it at the end. Same idea, same Big O.

Comparison

Standard Algorithms

All O(n): one pass through the list.

data = [1, 20, 39, 4, 12, 20, 4, 34, 2, 29, 20, 5, 66]

total = 0
count = 0
max_value = data[0]
max_index = 0
min_value = data[0]

for i in range(len(data)):
    total = total + data[i]              # sum
    if data[i] == 20:
        count = count + 1                # count occurrences
    if data[i] > max_value:
        max_value = data[i]              # maximum (and where it is)
        max_index = i
    if data[i] < min_value:
        min_value = data[i]              # minimum

average = total / len(data)
print(total, round(average, 2), count, max_value, max_index, min_value)
# 256 19.69 3 66 12 1

Start max and min at data[0], not 0. If every value were negative, a max starting at 0 would be wrong. Built in shortcuts: sum(), max(), min(), list.count(), but in exams write the loop.

Practice