Algorithms Notes | Leaving Cert Computer Science

Algorithmic Efficiency and Big-O Complexity

Algorithmic efficiency measures how the number of computational operations grows as the input size $n$ increases. It is expressed using Big-O notation. Big-O does not measure clock time in seconds; it reflects the rate of growth in operations.

Search and Sort Complexity Overview

Algorithm	Best-Case Time	Worst-Case Time	Behaviour and Key Characteristics
Linear Search	$O(1)$	$O(n)$	Checks elements sequentially one by one from the start. Works on unsorted data.
Binary Search	$O(1)$	$O(\log n)$	Divides the search range in half each step. Precondition: list must be sorted.
Simple Sort (Selection)	$O(n^2)$	$O(n^2)$	Always performs the full set of comparisons, even if the data is already sorted.
Bubble Sort	$O(n^2)$	$O(n^2)$	Compares adjacent pairs. ( $O(n)$ best-case applies only if an early-exit flag detects no swaps were made). Unless a flag is shown, assume $O(n^2)$ .
Insertion Sort	$O(n)$	$O(n^2)$	Highly efficient for nearly sorted data; quadratic if data is in reverse order.
Quicksort	$O(n \log n)$	$O(n^2)$	Divide-and-conquer algorithm; degrades to $O(n^2)$ if the pivot choices are repeatedly poor.

Schematic curves compare constant, logarithmic, linear, linearithmic and quadratic growth as input size increases.

Concrete Search Comparison

Searching for the value 23 in the sorted list [2, 5, 8, 12, 16, 23, 38] ( $n = 7$ ):

Linear Search: Compares 2, 5, 8, 12, 16, 23. It finds the item on the 6th comparison. If the target was absent or at the end, it would make 7 comparisons ( $n$ ).
Binary Search: Checks the middle element (index 3, value 12). Since $23 > 12$ , the left half is discarded. The sublist is [16, 23, 38]. It checks the new middle element (value 23), matching on the 2nd comparison. Doubling the list size adds only 1 extra comparison step ( $O(\log n)$ ).

Quadratic Growth: $O(n^2)$

If an algorithm has a complexity of $O(n^2)$ , doubling the input size from $n$ to $2n$ multiplies the number of operations by $2^2 = 4$ . Tripling the input size to $3n$ multiplies operations by $3^2 = 9$ .

Algorithmic Complexity and Big O Notation

Rather than timing code in seconds—which changes depending on the computer processor used—we measure algorithmic efficiency using Big O notation. Big O describes how an algorithm's running time or memory usage scales as the input size $n$ increases.

To see why this matters, consider input growth: if a list grows from 10 to 100 items ( $10 \times$ larger), an $O(n)$ algorithm performs 10 times more operations, while an $O(n^2)$ algorithm performs $10^2 = 100$ times more operations.

Complexity	Name	How Operations Grow	Example
$O(1)$	Constant Time	Unaffected by input size	Reading a list element at a known index (`L[0]`)
$O(\log n)$	Logarithmic Time	Halves the remaining data space at each step	Binary search on a sorted list
$O(n)$	Linear Time	Grows directly in proportion to $n$	Linear search across a list
$O(n \log n)$	Log-Linear Time	Divides data efficiently while recombining	Quicksort in best and average cases
$O(n^2)$	Quadratic Time	Grows with the square of $n$ ; doubling $n$ quadruples work	Nested loops in bubble sort, simple sort, insertion sort

Schematic curves compare constant, logarithmic, linear, log-linear and quadratic growth.

Complexity is evaluated across three conditions:

Best case: the minimum number of steps needed under ideal input conditions.
Average case: the typical number of operations required for randomly ordered data.
Worst case: the maximum number of operations required for the least favourable data arrangement.

Searching Algorithms: Linear and Binary Search

Searching algorithms find the position of a target item in a list.

Linear Search

Linear search examines each item sequentially from index 0 until the target is located or the list ends. It works on unsorted and sorted lists alike.

# Using a while loop with a found flag
names = ["John", "Mary", "Zoe", "Alex", "Séamas"]
target = "Zoe"
found = False
index = 0

while not found and index < len(names):
    if names[index] == target:
        found = True
    else:
        index += 1

Best case: 1 comparison (target is at index 0), so $O(1)$ .
Average case: checks roughly half the list ( $n/2$ steps), so $O(n)$ .
Worst case: $n$ comparisons (target is the last item or absent), so $O(n)$ .

Binary Search

Binary search works by repeated halving. It compares the target with the middle element. If the target matches, the search ends; if smaller, the search continues in the left half; if larger, it continues in the right half. The essential prerequisite is that the list must be sorted.

def binary_search(numbers, target):
    low = 0
    high = len(numbers) - 1
    while low <= high:
        mid = (low + high) // 2
        if numbers[mid] == target:
            return mid
        elif numbers[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # Target not in list

Searching for 42 narrows indices 0–8 to 5–8, then to index 5.

Best case: 1 comparison (target is at the initial midpoint), so $O(1)$ .
Average and worst case: halving means a list of size $n$ takes roughly $\log_2 n$ comparisons, so $O(\log n)$ .

Each doubling of the list size adds just one comparison. A list of 1,000 items takes at most 10 comparisons ( $2^{10} = 1024$ ), while 1,000,000 items takes only about 20 comparisons.

If you only need to run a single search on an unsorted list, linear search ( $O(n)$ ) is faster overall than sorting first ( $O(n \log n)$ ) just to run a binary search. If you need to search the same data repeatedly, sorting it once and using binary search saves time.

Simple Sort and Insertion Sort

Sorting organizes items into ascending or descending order. The data elements must be comparable.

Simple Sort (often taught as Selection Sort)

The syllabus lists 'Simple sort'. In classroom practice, simple sort is usually taught as repeatedly finding the smallest remaining item in the unsorted section and placing it into its correct position at the front, which is identical to selection sort.

def simple_sort(numbers):
    n = len(numbers)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if numbers[j] < numbers[min_index]:
                min_index = j
        numbers[i], numbers[min_index] = numbers[min_index], numbers[i]
    return numbers

Trace on [29, 10, 14, 37, 13]:

Pass 1: find minimum (10), swap with index 0 $\rightarrow$ [10, 29, 14, 37, 13]
Pass 2: find minimum from index 1 (13), swap with index 1 $\rightarrow$ [10, 13, 14, 37, 29]
Pass 3: find minimum from index 2 (14), already at index 2 $\rightarrow$ [10, 13, 14, 37, 29]
Pass 4: find minimum from index 3 (29), swap with index 3 $\rightarrow$ [10, 13, 14, 29, 37]

Simple sort scans every unsorted item in every pass, so best, average, and worst cases are all $O(n^2)$ .

Insertion Sort

Insertion sort mimics sorting a hand of playing cards. It steps through the list, picks the next item (the key), and shifts larger items in the sorted portion one slot to the right until the key reaches its place.

def insertion_sort(numbers):
    for i in range(1, len(numbers)):
        key = numbers[i]
        j = i - 1
        while j >= 0 and numbers[j] > key:
            numbers[j + 1] = numbers[j]  # Shift right
            j -= 1
        numbers[j + 1] = key
    return numbers

Trace on [5, 2, 4, 1]:

$i = 1$ , key = 2: $5 > 2$ , shift 5, insert 2 $\rightarrow$ [2, 5, 4, 1]
$i = 2$ , key = 4: $5 > 4$ , shift 5, stop before 2, insert 4 $\rightarrow$ [2, 4, 5, 1]
$i = 3$ , key = 1: shift 5, 4, and 2, insert 1 at index 0 $\rightarrow$ [1, 2, 4, 5]

With key 1 saved, the sorted prefix 2, 4, 5 shifts right before 1 is inserted at index 0.

Best case: $O(n)$ when the list is already sorted. Each item is compared once with its neighbour on the left, requiring 0 shifts.
Average and worst case: $O(n^2)$ . A reversed list requires comparing and shifting past every item in the sorted section.

Bubble Sort

Bubble sort steps through a list, compares adjacent items, and swaps them if they are out of order. With each complete pass, the largest remaining item moves to the end of the unsorted segment.

def bubble_sort(numbers):
    n = len(numbers)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True
        if not swapped:
            break  # Early exit if no swaps occurred
    return numbers

Understanding Bubble Sort Complexity

The best-case complexity depends on whether the code includes an early-exit flag:

Basic Bubble Sort (no flag): runs every pass regardless of order. It performs roughly $n^2 / 2$ comparisons on every list, meaning its best and worst cases are both $O(n^2)$ .
Optimised Bubble Sort (with swapped flag): stops after one pass if no swaps are made. On an already sorted list, it makes $n - 1$ comparisons and terminates, giving a best-case complexity of $O(n)$ .
In the worst case (a reverse-sorted list), both versions make the maximum number of comparisons and swaps: $O(n^2)$ .

Recursion and Quicksort

A recursive function is a function that calls itself to solve smaller instances of the same problem. Every recursive algorithm requires two components:

A base case, which stops recursion and returns a result directly without another call.
A recursive case, which calls the function again with inputs closer to the base case.

def factorial(n):
    if n <= 1:          # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

Tracing factorial(4):

factorial(4) waits for $4 \times \text{factorial}(3)$
factorial(3) waits for $3 \times \text{factorial}(2)$
factorial(2) waits for $2 \times \text{factorial}(1)$
factorial(1) hits the base case and returns 1.

The pending calls resolve backwards: $2 \times 1 = 2$ , then $3 \times 2 = 6$ , then $4 \times 6 = 24$ . If the base case is missing or never reached, the program will trigger a RecursionError by exceeding Python's call limit.

Factorial calls descend from 4 to 1, then return values 1, 2, 6 and 24 as pending multiplications resolve.

Quicksort

Quicksort is a divide-and-conquer algorithm. It selects an item as a pivot, creates sublists of items smaller than, equal to, and greater than that pivot, and sorts the smaller and larger sublists recursively.

def quicksort(numbers):
    if len(numbers) <= 1:      # Base case
        return numbers

    pivot = numbers[len(numbers) // 2]
    left = [x for x in numbers if x < pivot]
    middle = [x for x in numbers if x == pivot]
    right = [x for x in numbers if x > pivot]

    return quicksort(left) + middle + quicksort(right)

Pivot Selection and Partition Balance

Best and average case: $O(n \log n)$ . Occurs when the pivot divides the list into roughly equal halves, producing a balanced recursion tree.
Worst case: $O(n^2)$ . Occurs when the pivot is repeatedly the extreme smallest or largest element. This produces an unbalanced partition where one sublist contains $n - 1$ items and the other contains 0, eliminating the advantage of divide-and-conquer.

For example, in the list [60, 30, 80, 40, 10, 50, 20, 70, 90], picking 90 as the pivot places all 8 other items into the left sublist and leaves the right sublist empty, creating a worst-case partition.

Pivot 60 produces left and right groups of five and three items; pivot 90 produces groups of eight and zero.

Comparing Algorithms and Using Heuristics

Choosing the right algorithm depends on data size, whether the data is already ordered, and memory constraints.

Algorithm	Advantages	Limitations
Linear Search	Simple to code; works on unsorted data	Slow on large datasets: worst case $O(n)$
Binary Search	Fast on large datasets: $O(\log n)$	Data must be sorted first; harder to write
Simple Sort	Easy to trace; makes at most $n - 1$ swaps	Always $O(n^2)$ comparisons, even if sorted
Insertion Sort	Fast on nearly sorted lists: best case $O(n)$ ; sorts in place	Average and worst case are $O(n^2)$
Bubble Sort	Simple logic; early-exit flag detects sorted lists	Slow in practice: makes many swaps; worst case $O(n^2)$
Quicksort	Very fast on large datasets: average $O(n \log n)$	Degrades to $O(n^2)$ with poor pivots; recursive calls use call-stack memory

Heuristics

Some problems have so many combinations that checking every possibility would take years, even on supercomputers. For example, in the Travelling Salesperson Problem (finding the shortest route visiting $n$ cities), 20 cities produce more than $10^{16}$ different possible routes, far too many to check one by one.

When calculating an exact answer is impractical, computer scientists use a heuristic: a practical problem-solving method designed to find a good-enough solution quickly.

Nearest Neighbour Heuristic:

Start at any city.
Always visit the closest unvisited city next.
When all cities have been visited, return to the start.

This delivers a usable route in seconds. However, because each local decision is made without seeing the full map, an early choice might force a long leg at the end.

When to use heuristics: when computing resources or time are limited, and an approximate answer is acceptable (such as sat-nav routing, video game AI, or delivery scheduling).
When to avoid heuristics: when an exact, guaranteed answer is mandatory (such as banking transactions, cryptography, or medical drug dosages).
Trade-offs: using a heuristic can involve a loss of precision, accuracy, optimal performance, or completeness.

Algorithms