Each of the three steps of the Eagle algorithm involves an all-pairs O(MN2) computation (M = number of SNPs, N = number of samples) followed by an additional computation; the latter computation is inexpensive for step 1 and scales close to linearly with N for steps 2 and 3 (Supplementary Table 2). Thus, the distribution of time spent per step changes slightly with sample size, but no specific step is asymptotically a bottleneck. Summing across the three steps, the all-pairs O(MN2) computation constitutes slightly over half of the total computational cost at N≈150,000 (Supplementary Table 2).
