  We consider the problem of efficiently constructing polar codes over binary
memoryless symmetric (BMS) channels. The complexity of designing polar codes
via an exact evaluation of the polarized channels to find which ones are "good"
appears to be exponential in the block length. In \cite{TV11}, Tal and Vardy
show that if instead the evaluation if performed approximately, the
construction has only linear complexity. In this paper, we follow this approach
and present a framework where the algorithms of \cite{TV11} and new related
algorithms can be analyzed for complexity and accuracy. We provide numerical
and analytical results on the efficiency of such algorithms, in particular we
show that one can find all the "good" channels (except a vanishing fraction)
with almost linear complexity in block-length (except a polylogarithmic
factor).
