Asymptotic Analysis, Recurrence Relations, Master Theorem & Sorting

In theoretical computer science, algorithms are analysed on the Word RAM (Random Access Machine) model: a hypothetical computer where memory consists of an unbounded array of words, and primitive operations (arithmetic $+, -, \times, \div$, logical comparisons, array indexing, and variable assignment) on word-sized operands execute in $\Theta(1)$ constant time.

Rather than counting every machine instruction, we identify the Basic Operation—the most significant operation inside the deepest loop (such as key comparison in sorting/searching, or arithmetic multiplication in matrix algorithms)—and express its count $f(n)$ as a growth function of the input size $n$ across Best-Case, Worst-Case, and Average-Case inputs. Note that in the HESS notes:

• Growth Function Restrictions: Any valid complexity growth function $f(n)$ must satisfy two mathematical domain/range restrictions: $n \in \mathbb{N} = \{1, 2, 3, \dots\}$ (input sizes are positive integers) and $\forall n \in \mathbb{N},\; f(n) \ge 0$ (step counts are non-negative).
• Average-Case Complexity Warning: The Average-Case complexity is determined using probability and statistical expectation over the distribution of all possible inputs of size $n$—it is not simply the arithmetic mean of the Best Case and Worst Case!

The running time of a recursive algorithm is naturally expressed as a recurrence relation consisting of a recursive step (for $n > n_0$) and a base case (e.g., $T(1) = c$). Note that by Church-Turing equivalence, every recursive function can be converted into an iterative function (using an explicit loop/stack) and vice versa. In VCE Algorithmics, recurrences that are not in Master Theorem form (such as decrease-by-one $T(n - 1)$ recurrences) are solved into closed form via Iteration (Backward/Forward Substitution) or Telescoping Sums.

Essential Closed-Form Summation Identities

For divide-and-conquer algorithms that divide a problem of size $n$ into $a \ge 1$ subproblems, each of size $n / b$ (where $b > 1$), and spend $f(n) \in \Theta(n^k)$ work splitting and merging (where $k \ge 0$):

Binary Search locates a target value $x$ in a sorted array $A[0 \dots n-1]$ by comparing $x$ against the midpoint $m = \lfloor (\text{min} + \text{max}) / 2 \rfloor$ and discarding half of the remaining array each step.

In the HESS notes, Binary Search is rigorously classified as a Decrease-and-Conquer algorithm (specifically decrease-by-a-constant-factor) rather than Divide-and-Conquer, because it only recurses on one half ($a = 1$) and discards the other without any merge step.

Algorithm BinarySearch(A[0..n-1], target):
    min <- 0
    max <- n - 1
    While min <= max do:
        mid <- floor((min + max) / 2)
        If A[mid] == target then:
            Return mid
        Else If A[mid] < target then:
            min <- mid + 1
        Else:
            max <- mid - 1
        End If
    End While
    Return -1 // Not found
End Algorithm

Proving Greedy Algorithms Correct (The Two 4-Step HESS Proof Frameworks)

Because greedy algorithms do not always yield globally optimal solutions (for example, greedy coin-changing fails for coins $\{1, 3, 4\}$ with target $6$, picking $4+1+1$ instead of $3+3$), proving a greedy algorithm optimal requires one of two formal 4-step proof frameworks from the HESS notes:

Algorithm BackTrack(attempt, possible_options):
    If attempt is a complete solution then:
        Return attempt
    End if
    For each option in possible_options do:
        If option is valid for attempt then:
            add option to attempt
            result <- BackTrack(attempt, updated_options)
            If result != failure then:
                Return result
            End if
            remove option from attempt // Backtrack!
        End if
    End do
    Return failure
End Algorithm

Algorithm MergeSort(A[0..n-1]):
    Function Merge(Al[0..p-1], Ar[0..q-1], A[0..p+q-1]):
        i <- 0; j <- 0; k <- 0
        While i < p and j < q do:
            If Al[i] <= Ar[j] then:
                A[k] <- Al[i]; i <- i + 1
            Else:
                A[k] <- Ar[j]; j <- j + 1
            End If
            k <- k + 1
        End While
        If i == p then:
            Copy Ar[j..q-1] to A[k..p+q-1]
        Else:
            Copy Al[i..p-1] to A[k..p+q-1]
        End If
    End Function

    If n > 1 then:
        mid <- floor(n / 2)
        Copy A[0..mid-1] to Al
        Copy A[mid..n-1] to Ar
        MergeSort(Al)
        MergeSort(Ar)
        Merge(Al, Ar, A)
    End If
End Algorithm

Algorithm Quicksort(A, min, max):
    Function Partition(A, min, max):
        p <- min
        piv <- A[p]
        i <- min; j <- max
        Do:
            While i < max and A[i] <= piv do:
                i <- i + 1
            End While
            While j >= min and A[j] > piv do:
                j <- j - 1
            End While
            Swap A[i] <-> A[j]
        While i < j
        // Undo last swap when pointers crossed
        Swap A[i] <-> A[j]
        // Place pivot into final sorted position j
        Swap A[p] <-> A[j]
        Return j
    End Function

    If min < max then:
        s <- Partition(A, min, max)
        Quicksort(A, min, s - 1)
        Quicksort(A, s + 1, max)
    End If
End Algorithm

Key Comparison Analysis: Merge Sort vs Quick Sort

• Merge Sort ($\Theta(n \log n)$ in ALL cases & Bottom-Up Runs): Splitting $A$ into $A_L$ and $A_R$ creates two subproblems of size $n/2$. In the best case (all elements in $A_L$ are smaller than all elements in $A_R$), Merge performs $\lfloor n/2 \rfloor$ key comparisons. In the worst case (interleaved largest and second-largest elements), Merge performs $n - 1$ comparisons. In both cases, $T(n) = 2T(n/2) + \Theta(n) \in \Theta(n \log n)$ by Master Theorem Case 2. Merge Sort is stable (because Al[i] <= Ar[j] gives priority to the left element) and not in-place ($\Theta(n)$ auxiliary array space). Alternatively, Bottom-Up Merge Sort avoids recursion by treating the input array as $n$ sorted 1-element subarrays (called runs) and iteratively merging adjacent runs of size $1, 2, 4, 8, \dots$.
• Quick Sort Worst Case ($\Theta(n^2)$) vs Average Case ($\Theta(n \log n)$): When the pivot is chosen as the first element and the array is already sorted (or reverse sorted), every partition splits $n$ elements into an empty subarray of size $0$ and a subarray of size $n - 1$, degenerating Quick Sort from divide-and-conquer into decrease-by-one: $T(n) = T(n-1) + n \implies \sum_{i=2}^{n} i = \frac{n(n+1)}{2} - 1 \in \Theta(n^2)$. In the Average Case, random pivot splits require $\approx 2\ln(n) \approx 1.39\log_2(n)$ recursive levels and $\Theta(n \log n)$ key comparisons.
• Quick Sort Optimisations (HESS Notes):
  1. Random Pivot Selection or Median-of-Three Partitioning: Choose the median of $A[\text{min}]$, $A[\lfloor(\text{min}+\text{max})/2\rfloor]$, and $A[\text{max}]$ as the pivot (swapping the largest of the three candidates into A[max]), preventing $\Theta(n^2)$ degeneration on sorted inputs.
  2. Hybrid Insertion Sort Cutoff (QuickAlmostSort + InsertionSort): Stop Quick Sort recursion when subarray size is $\le 10$ (lo + 10 < hi), leaving small partitions nearly sorted, and finish with a single pass of InsertionSort over the entire array.

Algorithm Sort(A[lo..hi]):
    Function QuickAlmostSort(A[lo..hi]):
        If lo + 10 < hi then:
            s <- Partition(A[lo..hi])
            QuickAlmostSort(A[lo..s - 1])
            QuickAlmostSort(A[s + 1..hi])
        End if
    End Function

    QuickAlmostSort(A[lo..hi])
    InsertionSort(A[lo..hi])
End Algorithm

• I can solve decrease-by-one recurrences ($T(n-1)$) into exact closed form using Backward Substitution and Telescoping Sums.
• I can apply all three cases of the Master Theorem ($a < b^k, a = b^k, a > b^k$) and identify when the Master Theorem is inapplicable.
• I can prove Binary Search's loop invariant by mathematical induction and compare Merge Sort vs Quick Sort (Hoare Partitioning & Median-of-Three).