In equation (5), C(i) is the optimal cost for imputation from marker 1 to marker i and U(i,M) is the number of unique haplotypes between marker i and marker M (inclusive). This expression requires at most M2 comparisons; this number can be further reduced because we do not need to consider large segments, as the unique number of haplotypes in large segments will be close to the total number of haplotypes.
