Why Count the Work?
K-nearest neighbors (KNN) is simple to describe: compare a query case with the training cases, find the closest ones, and use their outcomes to make a prediction. That simplicity can conceal substantial computational cost. If a model must answer many queries against a large training set, repeatedly calculating distances may dominate the work. Cost estimates help determine whether a direct search is adequate, whether predictions can be batched, and whether a search index is worth building.
This tutorial focuses on the computation and storage required by brute-force search and on the conditions under which a search structure can help. These ideas support practical KNN use aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.
Brute-Force Search and Its Cost
In a brute-force search, each query is compared with every training case. For one query, this requires \(n\) distance calculations. For \(m\) queries, it requires \(mn\) distance calculations. This count assumes every query is external to the training set and all \(n\) cases are eligible neighbors. If a query is itself a training case and self-matches are excluded, there are \(n-1\) eligible cases for that query instead.
For predictor vectors \(x=(x_1,\ldots,x_p)\) and \(z=(z_1,\ldots,z_p)\), the squared Euclidean distance is
A squared distance is sufficient for ranking neighbors by Euclidean distance: the square-root function is increasing on nonnegative numbers, so \(D^2(x,z_1)<D^2(x,z_2)\) exactly when \(D(x,z_1)<D(x,z_2)\). A search that only needs the ordering therefore need not take a square root for every case.
The count \(3p-1\) follows directly from the formula: each coordinate contributes one subtraction and one multiplication, giving \(2p\) operations, and summing the \(p\) squared differences requires \(p-1\) additions. The total is \(2p+(p-1)=3p-1\). This is a stated counting convention, not a universal count for every implementation. For example, computing the ordinary Euclidean distance also requires a square root per case. A weighted distance may require additional multiplications unless its weights have been incorporated into a preprocessing transformation.
Worked Example: One Query Against 500 Stored Cases
A hypothetical portfolio model stores \(n=500\) training cases and uses \(p=5\) predictors in a squared Euclidean distance. One new query must be compared with every stored case. Count the distance calculations and the arithmetic operations, excluding neighbor selection.
Method. Brute force evaluates one distance for each training case, so the number of distances is \(n=500\).
For \(p=5\), one distance requires
arithmetic operations under the stated convention. The total is therefore
arithmetic operations. Check: \(500\) distances, each with \(14\) counted operations, gives \(7{,}000\), not \(14{,}500\). This method avoids confusing the number of distance calculations with the operations inside each calculation.
Fitting, Predicting, and Storing
KNN is often described as a lazy learner: fitting need not estimate regression coefficients or class probabilities. A basic fit stores the \(n\) training predictor vectors and their responses or class labels. If predictors are already prepared, storing the predictor values takes space proportional to \(np\), and storing one outcome per case adds space proportional to \(n\). Any scaling or other preprocessing has its own cost; it should not be counted as distance-search work unless it is performed as part of each query.
At prediction time, brute force performs \(n\) distance calculations per query, or \(mn\) for a batch of \(m\) queries. With squared Euclidean distances, this is \(mn(3p-1)\) arithmetic operations under the convention above, before comparisons and selection. Asymptotically, the distance work is \(O(mnp)\). The notation describes how work grows with the inputs; it does not specify an exact runtime in seconds.
It is possible to compute and store distances among training cases, for example to reuse them in a training-set analysis. That is an optional computation, not a necessary part of fitting a basic KNN model. Because distances are symmetric, a cache of all distinct unordered pairs contains \(n(n-1)/2\) values; a full ordered matrix contains \(n^2\) entries, including the diagonal. A pairwise cache can save later recalculation but costs \(O(n^2)\) storage, which may be much larger than storing the training cases themselves.
Worked Example: Batch Predictions and an Optional Training Cache
A hypothetical claims-screening model stores \(n=2{,}048\) cases with \(p=3\) predictors and must score \(m=6\) new cases. Assume squared Euclidean distance, all stored cases are eligible, and the operation count excludes selection. Find the batch prediction cost. Then find the size and calculation cost of an optional cache containing each distinct pairwise training distance once.
Prediction distance count. Each of six queries is compared with 2,048 stored cases:
distance calculations.
Prediction arithmetic. For \(p=3\), each squared distance requires
operations. The batch therefore requires
arithmetic operations, excluding selection and comparisons.
Optional cache. The number of distinct unordered training pairs is
Calculating each cached squared distance once requires
arithmetic operations. Check: the prediction count is \(12{,}288\), while the cache contains \(2{,}096{,}128\) distances. The cache is a separate training-time choice and does not replace the stated brute-force prediction calculation for new queries.
Selection and Storage Are Separate Costs
After calculating distances, a KNN procedure must identify the \(k\) smallest ones. A full sort of \(n\) distances generally takes \(O(n\log n)\) comparisons; a selection method can find the \(k\)th order statistic without fully sorting, and some implementations use a bounded heap. The precise work depends on the algorithm and whether the neighbors need to be ordered. Consequently, \(mn(3p-1)\) is an arithmetic count for the distance stage, not a complete operation count for an entire software prediction.
For a concrete storage estimate, suppose each predictor is stored as an 8-byte value and each class label as a 4-byte value. Ignoring identifiers, missingness indicators, alignment, indexes, and software overhead, the training data require \(n(8p+4)\) bytes. This estimate is only for the stated representation. A pairwise distance cache of \(n(n-1)/2\) values requires a further \(8n(n-1)/2\) bytes if each distance is stored in 8 bytes.
When Search Structures Help
A search structure organizes stored cases so that some regions can sometimes be ruled out without calculating a full distance to every case. For example, a tree can split predictor space into regions. During an exact query, the algorithm examines promising regions and uses geometric bounds to determine whether an unexplored region could contain a closer case than the current \(k\)th-best candidate. If the bound proves that it cannot, the region may be pruned.
Such structures can reduce the number of full point-to-query distance evaluations when the data geometry and query allow substantial pruning. Building the structure takes additional training time and storage, and the query must also perform navigation and bound calculations. Therefore, fewer full distances do not automatically imply a proportional reduction in total runtime. Exact search must retain enough candidates and inspect enough regions to certify the nearest neighbors; an approximate search may avoid more work, but it does not guarantee the exact neighbors.
A tree's performance is data-dependent. In favorable low-dimensional settings, a balanced index may visit only a fraction of the training cases. In difficult settings, including many high-dimensional problems, the bounds may be too weak to discard much of the data, and a query can require work on the order of a full scan. The curse of dimensionality makes geometric pruning less effective in many applications; an index should not be assumed to make search sublinear in every dataset.
Worked Example: Interpreting a Tree Search Bound
A hypothetical exact search index contains \(n=1{,}024\) cases with \(p=5\) predictors. For one query, the algorithm visits five leaves, each containing at most eight cases. Assume every case in a visited leaf receives a full squared-distance calculation and that the search's bounds certify that no unvisited leaf can contain a better neighbor. Find the maximum number of full distance calculations and the minimum reduction relative to brute force.
Candidate bound. Five leaves contain at most
cases in total. Thus the query requires at most 40 full distance calculations, not necessarily exactly 40.
At \(p=5\), each squared distance costs \(3(5)-1=14\) arithmetic operations, so the full-distance arithmetic is at most
This bound excludes the index's navigation and region-bound calculations.
Brute force would calculate \(1{,}024\) distances. Since the tree calculates at most 40, it avoids at least
full distance calculations. The fraction avoided is at least
or at least \(96.1\%\) when rounded to one decimal place. Check: the figures \(40\), \(560\), \(984\), and \(96.1\%\) are bounds because each leaf has at most eight cases; they would be exact only if all five leaves contained eight cases.
Common Cost-Counting Traps
- Multiplying by the wrong unit. \(mn\) counts distances for \(m\) queries against \(n\) cases. To count the arithmetic inside those distances, multiply again by the per-distance cost \(3p-1\), when that convention applies.
- Using \(3p\) instead of \(3p-1\). Summing \(p\) terms requires \(p-1\) additions, not \(p\). Under the stated count, \(p\) subtractions, \(p\) multiplications, and \(p-1\) additions total \(3p-1\).
- Treating a candidate upper bound as an exact count. If leaves contain at most a specified number of cases, the number of candidate distances is also an upper bound. Any claimed reduction from brute force is then a lower bound.
- Calling all query work “distance work.” Index navigation, region bounds, distance comparisons, and selecting the \(k\) nearest cases also take time. Keep these separate unless their costs have been specified.
- Assuming an index always helps. Search structures add construction and storage costs, and may visit most cases for an unfavorable query or high-dimensional dataset.
Check Your Understanding
For each problem, distinguish distance calculations from arithmetic operations and state any bounds as bounds.
- A model compares two new cases with \(n=360\) stored cases using \(p=4\) predictors and squared Euclidean distance. How many distances and distance-stage arithmetic operations are required? (Answer: 720 distances and 7,920 arithmetic operations.)
- A single query is compared with 900 eligible cases using \(p=6\) predictors. Excluding selection, how many squared-distance arithmetic operations are counted? (Answer: 15,300 arithmetic operations.)
- A training set has \(n=1{,}200\) cases and \(p=2\) predictors. A program caches each distinct unordered training-pair distance once, then separately predicts for \(m=4\) external queries by brute force. Give the cache distance count and arithmetic cost, and the prediction distance count and arithmetic cost. (Answer: 719,400 cached distances and 3,597,000 arithmetic operations; 4,800 prediction distances and 24,000 arithmetic operations.)
- An exact index for \(n=600\) cases with \(p=4\) visits seven leaves containing at most 12 cases each. If every visited case receives a full squared-distance calculation, what are the maximum candidate distance count and arithmetic count, and the minimum reduction in distances versus brute force? (Answer: At most 84 distances and 924 arithmetic operations; at least 516 distances avoided, or 86.0%.)
- A training set has \(n=2{,}500\) cases, \(p=8\) predictors, and one 4-byte label per case. If predictors use 8 bytes each, estimate the training-data storage while ignoring overhead. For \(m=10\) queries, also give the brute-force distance count and squared-distance arithmetic count. (Answer: 170,000 bytes; 25,000 distances and 575,000 arithmetic operations.)