# UPGMA

Unweighted pair group method with arithmetic mean (UPGMA) is a phylogeny reconstruction method.

Input
Matrix of pairwise distances
Output
Phylogeny
Algorithm
Repeatedly merge the nearest two clusters. The distance between clusters is the average of all pairwise distances between them. When merging two clusters, the distances of the new cluster are the weighted averages of distances from the two clusters being merged.
Complexity
$$O(n^3)$$ naive, $$O(n^2 \ln n)$$ using heap.