In the Decision tree model, the lower bound to be shown is the lower bound of the average length of root-to-leaf paths of an n ! {\displaystyle n!} -leaf binary tree (in which each leaf corresponds to a permutation). It would be convinced to say that a balanced full binary tree achieves the minimum of the average length. With some careful calculations, for a balanced full binary tree with n ! {\displaystyle n!} leaves, the average length of root-to-leaf paths is given by