Computational and Memory Costs of Hierarchical Clustering

Why Computational Cost Matters

Hierarchical clustering produces a nested sequence of merges, but an exact calculation can become demanding before the final dendrogram is available. The central issue is scale: with \(n\) observations there are many more than \(n\) pairs, and a straightforward algorithm may inspect a large set of active pairs again and again. Knowing the order of these costs helps determine whether a proposed analysis is feasible and whether a memory or time estimate is realistic.

The estimates below concern agglomerative hierarchical clustering of \(n\) observations using a symmetric dissimilarity: the dissimilarity between observations \(i\) and \(j\) equals that between \(j\) and \(i\), and an observation’s dissimilarity to itself is zero. The number of features is denoted by \(p\). Exact work depends on the distance measure, linkage rule, data structures, and implementation, so complexity statements describe an algorithm under stated assumptions rather than a universal running time.

Definition: A pairwise dissimilarity matrix records the dissimilarity for every pair of observations. Under symmetry and a zero diagonal, it contains \(n(n-1)/2\) distinct off-diagonal values. The time complexity describes how computational work grows with input size; the space complexity describes how required storage grows.

Quadratic Storage for Pairwise Dissimilarities

There are \(n\) choices for the first observation in an ordered listing of pairs and \(n-1\) choices for the second, giving \(n(n-1)\) ordered pairs of distinct observations. Each unordered pair appears twice in that count: once as \((i,j)\) and once as \((j,i)\). Symmetry therefore leaves

\binom{n}{2}=\frac{n(n-1)}{2}

distinct dissimilarities. This count grows approximately as \(n^2/2\), so storing a single value per distinct pair requires quadratic space, written \(O(n^2)\). The notation \(O(n^2)\) describes the growth rate as \(n\) becomes large; it does not specify a fixed number of bytes.

A full \(n\)-by-\(n\) array stores both copies of each off-diagonal dissimilarity, as well as the diagonal. It uses \(n^2\) entries, whereas a packed triangular representation can store only the \(n(n-1)/2\) distinct values. Both have \(O(n^2)\) space complexity, but the packed version uses close to half as many entries. A program may also allocate temporary arrays or keep the original feature matrix, cluster labels, sizes, and merge history. Those requirements are additional to the dissimilarity values.

If each distance is stored as an 8-byte floating-point number, the packed dissimilarities alone require \(8n(n-1)/2\) bytes. For a feature matrix with \(n\) rows and \(p\) stored numeric features, its entries take approximately \(8np\) bytes under the same assumption. These are estimates of raw numeric storage, not promises about a particular program’s total memory use.

Worked Example: Estimating Storage Before Clustering

A hypothetical analysis has \(n=5{,}000\) observations and \(p=20\) numeric features. Suppose one packed copy of the symmetric dissimilarity values is stored using 8 bytes per value, and the feature matrix is also retained in 8-byte numeric entries. Estimate their combined storage in MiB, where \(1\text{ MiB}=1{,}048{,}576\) bytes. Ignore software overhead.

Method. Count the distinct observation pairs, multiply by the bytes per distance, then add the feature-matrix storage. This avoids counting both halves of a symmetric matrix.

The number of distinct distances is \(5{,}000(4{,}999)/2=2{,}500(4{,}999)=12{,}497{,}500\). Their storage is \(12{,}497{,}500(8)=99{,}980{,}000\) bytes.

The feature matrix contains \(5{,}000(20)=100{,}000\) entries, so it uses \(100{,}000(8)=800{,}000\) bytes. The combined estimate is \(99{,}980{,}000+800{,}000=100{,}780{,}000\) bytes.

Convert to MiB: \(100{,}780{,}000/1{,}048{,}576\approx96.1114\) MiB. Rounded to two decimal places, the estimate is 96.11 MiB, excluding overhead. As a check, the distance matrix accounts for \(99{,}980{,}000\) of the \(100{,}780{,}000\) bytes, as expected when the matrix has many more entries than the feature data.

Common mistake avoided: using \(5{,}000^2\) entries for a packed matrix, which counts two copies of each pair and the diagonal. A full square array would use that many entries, but the packed representation in this problem does not.

Distance Calculation and Repeated Merge Searches

If each of the \(\binom{n}{2}\) initial distances is calculated from \(p\) features, and the work per feature is bounded by a constant number of arithmetic operations, the total distance-calculation work is \(O(n^2p)\). This assumes the chosen distance can be computed by examining the features of the pair. The constant and even the per-pair cost can differ across distance measures and data types. A distance involving a costly operation, for example, may take more work than one involving only simple arithmetic.

After the initial distances are available, a simple merge-selection strategy scans all pairs of currently active clusters to find the smallest dissimilarity. With \(k\) active clusters, that scan inspects \(\binom{k}{2}\) pairs. There are \(n-1\) merges: the active count falls from \(n\) to 2 before the last merge. If a complete scan is performed at every stage, the total number of pair inspections is

\sum_{k=2}^{n}\binom{k}{2} =\binom{n+1}{3} =\frac{n(n-1)(n+1)}{6}.

The sum identity follows because \(\binom{k}{2}=\binom{k+1}{3}-\binom{k}{3}\). Summing over \(k=2,\ldots,n\) cancels the intermediate terms, leaving \(\binom{n+1}{3}-\binom{2}{3}=\binom{n+1}{3}\). This repeated full-scan method therefore has \(O(n^3)\) merge-selection work. It is a clear baseline, not a claim that every implementation uses this strategy.

Worked Example: Counting Full-Scan Pair Inspections

A simple implementation clusters \(n=3{,}000\) observations and performs a complete pair scan at every merge-selection stage. How many pair inspections does it make across all stages?

Method. At a stage with \(k\) active clusters, count \(\binom{k}{2}\) inspections. Summing from \(k=2\) through \(3{,}000\) gives \(\binom{3{,}001}{3}=3{,}000(2{,}999)(3{,}001)/6\).

First multiply the factors around 3,000: \(2{,}999(3{,}001)=(3{,}000-1)(3{,}000+1)=3{,}000^2-1=8{,}999{,}999\). Also, \(3{,}000/6=500\). Thus the total is \(8{,}999{,}999(500)=4{,}499{,}999{,}500\) pair inspections.

The result is just under 4.5 billion inspections. The count refers to pair comparisons across all stages, not to the number of distinct distances initially calculated. The distinction matters because the full-scan method revisits pairs of active clusters at successive stages.

Common mistake avoided: using only \(\binom{3{,}000}{2}\), which counts the initial pairs but not the scans at later stages. The full sequence requires the sum over all active-cluster counts.

Linkage Updates and the Cost of Each Merge

Once two clusters merge, their dissimilarities to the remaining clusters must be available for the next step. When there are \(k\) active clusters before a merge, the new cluster needs a distance to each of the \(k-2\) clusters that did not merge. Across the entire procedure, the number of such updates is

\sum_{k=2}^{n}(k-2) =\sum_{r=0}^{n-2}r =\frac{(n-2)(n-1)}{2}.

Thus, if each update takes constant work using already available cluster distances and any required cluster-size information, all updates together take \(O(n^2)\) work. The condition about constant work is important. The Lance-Williams formula, covered in earlier material on updating cluster distances, expresses several linkage updates as a weighted combination of previously available distances; applying such an update takes a bounded number of arithmetic operations. A direct method that repeatedly revisits all original observations in both clusters need not have the same update cost.

A quadratic number of linkage updates does not by itself guarantee quadratic total runtime. A routine that still searches all active pairs from scratch at every stage can spend cubic work selecting the next merge. Conversely, data structures or specialized algorithms can reduce merge-selection work for particular linkage rules, but their guarantees depend on the method and its conditions. The \(O(n^3)\) count above applies specifically to the repeated full scan; it should not be attributed automatically to every exact hierarchical clustering implementation.

Worked Example: Separating Distance, Update, and Search Work

A hypothetical data set has \(n=2{,}400\) observations and \(p=12\) numeric features. Assume each feature contributes a bounded amount of work to calculating a pairwise distance. Compare (a) the number of feature-coordinate contributions for all initial distances, (b) the number of linkage updates if one update is made for each unaffected active cluster after each merge, and (c) full-scan pair inspections over all stages.

Method. Use \(\binom{n}{2}p\) for coordinate contributions, \((n-1)(n-2)/2\) for linkage updates, and \(\binom{n+1}{3}\) for repeated full scans. These counts describe different tasks and should not be added as if they were the same operation.

There are \(2{,}400(2{,}399)/2=1{,}200(2{,}399)=2{,}878{,}800\) initial pairs. At 12 feature contributions per pair, the total is \(2{,}878{,}800(12)=34{,}545{,}600\) coordinate contributions.

The update count is \(2{,}399(2{,}398)/2=2{,}399(1{,}199)\). Since \(2{,}399(1{,}200)=2{,}878{,}800\), subtracting \(2{,}399\) gives \(2{,}876{,}401\) updates.

For repeated full scans, \(\binom{2{,}401}{3}=2{,}400(2{,}399)(2{,}401)/6\). The product \(2{,}399(2{,}401)=2{,}400^2-1=5{,}759{,}999\), and \(2{,}400/6=400\). Therefore the scan count is \(5{,}759{,}999(400)=2{,}303{,}999{,}600\) pair inspections.

The calculation checks three different scales: about 34.5 million feature contributions, about 2.88 million linkage updates, and about 2.304 billion full-scan inspections. The scan count is much larger because it repeats the search across stages.

Common mistake avoided: treating one feature-coordinate contribution, one updated cluster distance, and one pair inspection as interchangeable units of work. They count different operations, and actual elapsed time also depends on the cost of each operation and the implementation.

Practical Feasibility and Common Traps

For exact hierarchical clustering that retains all initial pairwise dissimilarities, quadratic storage can become a limiting factor even when the number of features is modest. A packed representation reduces the constant factor but not the growth rate. If \(n\) doubles, the number of stored pairs is multiplied by approximately four. By contrast, the feature matrix has \(np\) entries, so for fixed \(p\) it grows linearly with \(n\). At sufficiently large \(n\), the pairwise values can dominate memory.

Time estimates require the same care. Initial distance calculation is commonly \(O(n^2p)\) under the per-feature assumption. Linkage updates can be \(O(n^2)\) in total when each update uses a constant amount of work. A repeated complete scan adds \(O(n^3)\) merge-selection work. These descriptions separate the main sources of cost, but they do not predict elapsed seconds without hardware, software, data representation, and operation costs.

Do not confuse distance storage with total program memory. Feature data, temporary work arrays, cluster bookkeeping, and software overhead may also be retained.
Do not infer a cubic cost from the definition of hierarchical clustering alone. The cubic estimate here belongs to a repeated full-scan search strategy; other algorithms can have different costs.
Do not count only the initial pair set when estimating full-scan work. A full scan is repeated as the number of active clusters decreases.
Do not assume a cheaper approximation has the same result. Sampling, sparse representations, or approximate methods may change the computed hierarchy or its guarantees; their use should be justified for the analysis.

A useful feasibility check is to estimate both bytes and operations before running the algorithm. Calculate the number of distinct pairs first, specify whether the representation is packed or square, and state which merge-search procedure is assumed. Then separate initial distance calculations, linkage updates, and merge selection. This makes the estimate interpretable and exposes hidden assumptions.

Key takeaway: A symmetric pairwise dissimilarity matrix has \(n(n-1)/2\) distinct values and therefore requires \(O(n^2)\) storage. Initial distance calculation is typically \(O(n^2p)\) under bounded per-feature work; linkage updates can total \(O(n^2)\), while repeated full scans of active pairs require \(O(n^3)\) merge-selection work.

Check Your Understanding

For each problem, state the relevant assumption and distinguish storage or operation counts from elapsed time.

A program stores one packed array of 8-byte dissimilarities for \(n=1{,}200\) observations. How many distance values are stored, and how many bytes do they occupy? (Answer: 719,400 values and 5,755,200 bytes, about 5.4886 MiB.)
A data set has \(n=800\) observations and \(p=7\) features. If each feature contributes a bounded amount of work to each initial pairwise distance, how many feature-coordinate contributions are required? (Answer: \(\binom{800}{2}(7)=319{,}600(7)=2{,}237{,}200\) contributions.)
A full-scan implementation clusters \(n=1{,}000\) observations. How many pair inspections does it make over all merge-selection stages? (Answer: \(\binom{1{,}001}{3}=1{,}000(999)(1{,}001)/6=166{,}666{,}500\) inspections.)
An update-based implementation makes one linkage update for each cluster unaffected by a merge. Across all stages for \(n=1{,}500\), how many updates are made? (Answer: \((1{,}499)(1{,}498)/2=1{,}122{,}751\) updates.)
A study has \(n=6{,}000\) observations and \(p=15\) features. Assuming one packed 8-byte distance per distinct pair and an 8-byte feature matrix, with no overhead, what is the combined storage in MiB? (Answer: \(17{,}997{,}000(8)+6{,}000(15)(8)=144{,}696{,}000\) bytes, or approximately 137.99 MiB.)

What You'll Learn