VCE Algorithmics (HESS) cheat sheet

Big-O describes an upper bound on growth: f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀; Big-Omega is the matching lower bound and Big-Theta means both hold.

Standard growth order from slowest to fastest: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!). Only the dominant term is kept and constant factors are dropped, so 3n² + 5n + 7 is Θ(n²).

Linear search is O(n) worst case and works on unsorted data; binary search is O(log n) but requires the array to be sorted, and each step halves the remaining search interval by comparing with the middle element.

Selection sort performs Θ(n²) comparisons in every case; insertion sort is O(n²) worst case but Θ(n) on already-sorted input; merge sort is Θ(n log n) in all cases and needs O(n) auxiliary space.

Quicksort averages Θ(n log n) but degrades to O(n²) when the pivot is consistently extreme (e.g. first element on sorted input); randomised or median-of-three pivot choice mitigates this.

A stack is LIFO (push/pop at one end) and a queue is FIFO (enqueue at rear, dequeue at front); both support O(1) insertion and removal when implemented with a linked list or circular array.

A hash table gives average O(1) lookup, insertion and deletion, but degrades toward O(n) per operation when many keys collide into the same bucket; load factor = entries ÷ buckets drives resizing.

Graph traversal: breadth-first search uses a queue and finds shortest paths in unweighted graphs in O(V + E); depth-first search uses a stack or recursion and supports cycle detection and topological ordering in O(V + E).

Recurrence solving: a divide-and-conquer recurrence T(n) = aT(n/b) + f(n) yields Θ(n^log_b a) when f(n) is smaller, and Θ(f(n)·log n) when f(n) matches the recursive term, as in merge sort's T(n) = 2T(n/2) + Θ(n).

A decision problem is in P if it can be solved in polynomial time; it is in NP if a proposed certificate can be verified in polynomial time, so P ⊆ NP (whether P = NP is open).

NP-complete problems (e.g. SAT, 3-SAT, Hamiltonian cycle, subset sum, travelling salesman decision version) are the hardest problems in NP: every NP problem reduces to them in polynomial time.

To prove a new problem is NP-complete: (1) show it is in NP by exhibiting a polynomial-time verifier, and (2) give a polynomial-time reduction from a known NP-complete problem to it.

A reduction from A to B means solving B solves A; therefore if A is NP-hard then B is NP-hard, and if B is in P then A is in P (contrapositive: hardness transfers forward along the reduction).

Intractable problems are handled by approximation algorithms with a guaranteed ratio bound, heuristics (greedy, local search), or exact methods with pruning such as branch-and-bound that perform well on typical inputs.

Undecidability: the halting problem cannot be decided by any algorithm; a problem is undecidable if no algorithm always terminates with the correct yes/no answer, and such problems lie outside NP entirely.

Turing machines formalise computability: a finite state control, an infinite tape and a read/write head; a language is decidable if some Turing machine halts on every input with the correct answer.

Correctness reasoning: a loop invariant must hold before the loop, be preserved by each iteration, and combined with loop termination imply the postcondition; induction on input size proves recursive algorithm correctness.

Ethical and legal obligations: privacy of personal data, algorithmic bias from unrepresentative training data, transparency of automated decisions, and compliance with Australian privacy law shape how algorithms are deployed.