Finally, to tie this discussion off, two truly official references that explicitly address the issue of runtime complexity. In the best case, as determined by

Finally, to tie this discussion off, two truly official references that explicitly address the issue of runtime complexity. In the best case, as determined by Halko et al., you low-rank k approximation of a n times m term-document matrix is O(nmk), and randomized approximations get that down to O(nm log(k)) [1]. And, according to Rehurek's own investigations [2], those approximated eigenvectors are typically good enough. I.e., in both cases, the decomposition scales with the product of documents and words, not their sum. Therefore, this is clearly not a linear problem. On top of that, when these inverted indices grow too large to be computed on a single machine, earlier methods required k passes over the data. These newer approaches [1,2] can make do with a single pass, meaning that the thing that indeed scales linearly here is the performance gains of scaling your SVD among a cluster with these newer approaches. Maybe this is the source of confusion for some commenters here. [1] https://authors.library.caltech.edu/27187/ https://authors.library.caltech.edu/27187/ [2] https://link.springer.com/chapter/10.1007%2F978-3-642-20161-5_29 https://link.springer.com/chapter/10.1007%2F978-3-642-20161-...