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