title: A question about the time-complexity of msd algorithm
body: <p>Recently I have been reading Algorithm 4.It says knuth has prove that the average check of chars in msd algorithm is NlgN,so why the time-complexity of this algorithm is not log-linear but linear?
  If we use check of chars as cost model,should the time-complexity change to log-linear?</p>