Classifying Algorithms by Time and Space Complexity

Why Classify Algorithms?

Different algorithms solve the same problem but with different resource requirements. Complexity analysis provides a principled way to:
- Compare algorithms independent of hardware
- Predict performance as input size grows
- Determine feasibility for large inputs

KEY TAKEAWAY: Complexity classifies how an algorithm’s resource usage (time or space) scales with input size $n$. This tells us whether an algorithm is practical for large inputs.

Time Complexity

Time complexity measures how the number of fundamental operations grows as a function of input size $n$.

Input size $n$ may represent: number of elements in an array, number of vertices/edges in a graph, value of a number, etc.
We count operations (comparisons, assignments, additions), not actual seconds
Focus on the dominant term as $n \to \infty$

Example:

for i ← 0 to n-1 do
    for j ← 0 to n-1 do
        A[i][j] ← 0
    end for
end for

This performs $n^2$ assignments. Time complexity: $O(n^2)$.

Space Complexity

Space complexity measures how much memory an algorithm uses as a function of $n$.

Auxiliary space: Extra space beyond the input itself
Includes variables, data structures created during execution

Example:
- In-place sorting (e.g., Quicksort): $O(\log n)$ auxiliary space (call stack)
- Mergesort: $O(n)$ auxiliary space (temporary array for merging)
- Floyd-Warshall: $O(n^2)$ space (distance matrix)

Time vs. Space Tradeoffs

Often, using more space allows faster computation:
- Memoisation (dynamic programming): Store computed results to avoid recomputation — trades space for time
- Hash tables: Use extra memory for $O(1)$ lookup vs. $O(n)$ search in a list

Input Size and What It Represents

Problem	$n$ represents
Sorting	Number of elements
Graph algorithms	Number of vertices $V$ and/or edges $E$
String algorithms	Length of the string
Number theory	Magnitude of the number (or its number of digits)

EXAM TIP: Always specify what $n$ represents when stating complexity. “The algorithm runs in $O(n^2)$” is incomplete without “where $n$ is the number of vertices.”

Summary of Common Complexities

Complexity	Name	Example
$O(1)$	Constant	Array access, hash table lookup
$O(\log n)$	Logarithmic	Binary search, heap operations
$O(n)$	Linear	Linear search, single-pass scan
$O(n \log n)$	Log-linear	Mergesort, Quicksort (average)
$O(n^2)$	Quadratic	Bubble sort, Floyd-Warshall $O(n^3)$
$O(2^n)$	Exponential	Brute-force subsets
$O(n!)$	Factorial	Brute-force permutations

VCAA FOCUS: Be able to classify the time and space complexity of a given algorithm by analysing its structure. Also be able to argue why a complexity class is appropriate (not just state it).

Time and Space Complexity Classification

Table of Contents

About these notes

Join StudyPulse