Actually, it doesn't increase much faster than linear. It's quasilinear, and so in O(n^(1+\epsilon) for all \epsilon > 0. There are a variety of such results, s

Actually, it doesn't increase much faster than linear. It's quasilinear, and so in O(n^(1+\epsilon) for all \epsilon > 0. There are a variety of such results, so most objections don't hold weight. The paper you linked to names challenges, but it only states those in respect to reaching practical scaling, which is a result of the constant that is associated with the growth rate, but not the growth rate itself.