Methods that perform phasing and imputation simultaneously (for example, MaCH29 and IMPUTE31) have a computational cost proportional to the number of study samples (N), the number of genotyped markers in the reference panel (M), and the square of the number of reference haplotypes (H2), or in total O(NMH2). In the context of prephasing, as in minimac and IMPUTE2 (ref. 9), this computational cost is reduced to O(NMH).
