As with complete linkage and average distance, the difficulty of calculating cluster distances causes the nearest-neighbor chain algorithm to take time and space {{math|''O''(''n''<sup>2</sup>)}} to compute the single-linkage clustering.
However, the single-linkage clustering can be found more efficiently by an alternative algorithm that computes the [[minimum spanning tree]] of the input distances using [[Prim's algorithm]], (withand anthen unsortedsorts listthe ofminimum verticesspanning tree edges and theiruses prioritiesthis insorted placelist ofto guide the usualmerger priorityof queue),pairs andof thenclusters. sortsWithin thePrim's algorithm, each successive minimum spanning tree edgesedge andcan usesbe thisfound sortedby a [[sequential search]] through an unsorted list of the smallest edges connecting the partially constructed tree to guideeach additional vertex. This choice saves the mergertime ofthat pairsthe algorithm would otherwise spend adjusting the weights of clustersvertices in its [[priority queue]]. ThisUsing alternativePrim's algorithm in this methodway would take time {{math|''O''(''n''<sup>2</sup>)}} and space {{math|''O''(''n'')}}, matching the best bounds that could be achieved with the nearest-neighbor chain algorithm for distances with constant-time calculations.<ref>{{citation
