A faster algorithm is not always the better choice. Performance must be measured against the job at hand: how long operations take, how much memory they use, and—when results can be approximate—how good those results are. Start by naming the operation or output that matters, then compare alternatives under the same relevant conditions. section 3.5.3 section 11.3.1
Use different measures for different questions:
- Running time describes the cost of operations as inputs grow. Compare the operations an application actually performs, not just a structure’s headline complexity. section 2.5.1 section 14.4.3
- CPU profiling measures a particular implementation on particular test data. It can reveal costs that an asymptotic bound or structural measure, such as tree height, does not settle. section 3.5.3
- Memory and result quality are separate considerations. A Bloom filter’s operation times can be examined alongside the precision of `contains`; clustering needs a measure of output quality as well as an analysis of computational cost. section 4.9 section 12.5
When the input changes the winner
CPU profiling of insertion and removal found a randomized treap slower than a BST for random, unbounded integer keys: insertion took almost twice the cumulative CPU time, and removal 3.5 times as much. With random keys restricted to [0, 1000], the BST’s height grew linearly and the comparison reversed: BST insertion took eight times as long as treap insertion, with removal showing almost a 15-fold treap speed-up. Treat either result as evidence about the tested implementations and workloads, not a universal ranking. section 3.5.3
For an analytical estimate, count the work in each repeated operation and state the input variables. K-means, for example, takes O(m·k·n·d) time for at most m iterations, k clusters, n points, and d dimensions, plus O(n+k) extra memory. That estimate answers a different question from profiling elapsed CPU time. section 12.2.3 section 3.5.3
Quality when clusters cannot be judged by eye
Customer segmentation using annual income and monthly spending illustrates why output quality needs deliberate evaluation. In higher dimensions, visual inspection is difficult; without feature scaling, the larger-valued feature can dominate Euclidean distance. An elbow-method procedure tests candidate cluster counts, runs k-means repeatedly for each count, and records the minimum intra-cluster distance from those runs. section 12.5
In a time-limited nearest-neighbor service, average speed may help serve more requests, while worst-case speed may help ensure requests finish before a deadline. If data growth makes exact search too slow, sharding or an approximate approach may help, but approximation trades some result accuracy for speed. Choose the measure—and the compromise—that matches the constraint. section 11.3.1
