Scaling Analysis and Log-Log Plots

Overview

Empirically assessing algorithmic complexity involves measuring runtime (or operation count) against input size and plotting the data. Log-log and log-linear plots reveal the functional form of the growth rate. This technique helps distinguish polynomial, linearithmic, and exponential behaviour without requiring a theoretical analysis.

The Log-Log Plot

If runtime $T(n)$ follows a power law: $T(n) \approx c \cdot n^k$, then taking logs:

$\log T(n) = \log c + k \log n$

On a log-log plot (both axes logarithmic), this is a straight line with slope $k$. The constant $c$ determines the vertical intercept.

The slope $k$ directly estimates the polynomial degree of the algorithm’s growth. Linear regression on log-transformed data can estimate $k$ from empirical measurements.

Recognising Growth Patterns

On a log-log plot:

Curve shape	Growth rate
Flat horizontal line	$\Theta(1)$ (constant)
Gentle upward curve (concave)	$\Theta(\log n)$
Straight line with slope 1	$\Theta(n)$
Straight line with slope slightly $>$ 1	$\Theta(n \log n)$ (appears nearly straight but slightly curved on log-log)
Straight line with slope 2	$\Theta(n^2)$
Near-vertical	$\Theta(2^n)$ (exponential)

On a log-linear plot (y-axis logarithmic, x-axis linear), exponential growth appears as a straight line: $\log T(n) = \log c + n \log a$ for $T(n) = c \cdot a^n$.

Example: Heart Rate and Lifespan

A classic data set from Levine (1997, Journal of the American College of Cardiology) plots resting heart rate against average lifespan across mammal species. The raw scatter plot appears hyperbolic, suggesting an inverse relationship:

$\text{heart rate} \times \text{lifespan} \approx \text{constant}$

Equivalently, $\log(\text{heart rate}) + \log(\text{lifespan}) = \text{constant}$. A log-log plot transforms this into a straight line with slope $-1$, confirming the relationship $\text{heart rate} \propto (\text{lifespan})^{-1}$. This is the same technique applied to biological scaling rather than algorithmic scaling.

Applying to Algorithm Analysis

Given empirical timing data for various input sizes $n_i$ with measured runtimes $t_i$:

1. Plot $(\log n_i, \log t_i)$.
2. Fit a linear regression to estimate the slope $k$.
3. If $k \approx 1$, the algorithm is $\Theta(n)$. If $k \approx 2$, it is $\Theta(n^2)$.

Caution: $\Theta(n \log n)$ does not produce a perfectly straight line on a log-log plot; it is slightly curved. To distinguish $n \log n$ from $n$, you can plot $T(n)/n$ against $\log n$ — the former should appear linear.

Summary

Property	Value
Purpose	Empirically determine algorithmic growth rate
Power law $c n^k$	Straight line with slope $k$ on log-log
Exponential	Straight line on log-linear
$n \log n$	Slightly curved on log-log; linear on $T(n)/n$ vs. $\log n$
Slope $< 0$	Decreasing function (e.g. inverse relationship)