Computational Complexity - Executable Engineering: Interactive Numerical Methods in Python

import numpy as np
import time
import plotly.graph_objects as go

try:
    import executable_engineering as exe
except ImportError:
    %pip install -q executable_engineering
    import executable_engineering as exe

Measuring Performance¶

When writing numerical methods, we need to compare how fast different algorithms are. However, execution time depends on the computer’s hardware.

Instead, we use computational complexity to characterize the number of operations an algorithm requires based on the size of its inputs (e.g., vector length $n$ , or matrix size $n \times n$ ).

Big-O Notation¶

Complexity is represented using Big-O notation ( $\mathcal{O}$ ).

Similar to how we tracked the leading order of truncation error, Big-O notation only keeps the dominant leading term and disregards scalar constants as $n$ becomes very large.

$\mathcal{O}(n)$ : Linear time (complexity). Doubling the input size doubles the operations.
$\mathcal{O}(n^2)$ : Quadratic time. Doubling the input size quadruples the operations.
$\mathcal{O}(n^3)$ : Cubic time. Doubling the input size multiplies operations by 8.

Example: Matrix Multiplication¶

Traditional matrix multiplication of two $n \times n$ matrices requires multiplying every row of $\mathbf{A}$ by every column of $\mathbf{B}$ .

There are $n^2$ elements in the resulting matrix.
Calculating each element requires a dot product of length $n$ .
Total operations: $n^2 \times n = n^3$ .

Therefore, standard matrix multiplication is $\mathcal{O}(n^3)$ .

Note: This is algorithm-dependent! Advanced algorithms (like the Strassen algorithm) can achieve $\mathcal{O}(n^{2.81})$ by cleverly reusing sub-calculations.

Profiling Execution Time¶

Let’s prove this by actually timing matrix multiplication in Python for different matrix sizes $n$ , and plotting the execution time!

NB: Techincally this profiles the time, not the # of operations. It is however a useful and quick surrogate.

sizes = [100, 200, 400, 800, 1600]
times = []

for n in sizes:
    A = np.random.rand(n, n)
    B = np.random.rand(n, n)
    
    start_time = time.perf_counter()
    C = A @ B
    end_time = time.perf_counter()
    
    times.append(end_time - start_time)
    print(f"n={n:4d} | time={times[-1]:.4f} seconds")

# Plotting the results
fig = go.Figure()
fig.add_trace(go.Scatter(x=sizes, y=times, mode='lines+markers', name='Measured Time'))

# Fit a cubic curve (y = c * n^3) for comparison
c = times[-1] / (sizes[-1]**3)
cubic_fit = [c * (n**3) for n in sizes]
fig.add_trace(go.Scatter(x=sizes, y=cubic_fit, mode='lines', name='O(n³) Theoretical', line=dict(dash='dash')))

fig.update_layout(title="Matrix Multiplication Complexity", xaxis_title="Matrix Size (n)", yaxis_title="Time (seconds)")
fig.show()

Common Linear Algebra Operations¶

Here is the computational complexity for standard operations on $n \times n$ matrices:

Operation	Description	Complexity
Matrix addition	Adding two matrices	$\mathcal{O}(n^2)$
Matrix norm	Square root of sum of squares	$\mathcal{O}(n^2)$
Transpose	Swapping rows and columns	$\mathcal{O}(n^2)$
Matrix-vector mult	Multiplying a matrix by a vector	$\mathcal{O}(n^2)$
Matrix multiplication	Multiplying two matrices	$\mathcal{O}(n^3)$
Matrix inversion	Finding the exact inverse	$\mathcal{O}(n^3)$
Determinant	Computing the determinant	$\mathcal{O}(n^3)$

Scaling in Parallel Computing¶

High-performance computing introduces a new element to complexity: scaling.

Instead of asking how execution time grows with input size $n$ , scaling asks how execution time decreases as we add more parallel hardware (CPU cores or compute nodes).

This is measured in $\mathcal{O}(\text{number of nodes})$ . The ultimate goal is perfectly linear scaling $\mathcal{O}(N)$ , meaning 100 computers will solve the problem 100 times faster—but due to communication overhead, this is notoriously difficult to achieve!