2 ms·
They mention O(n log* n) being quasi linear time, I had to look up log * n because I never saw this before.
by carlmr 7y ago
They mention O(n log* n) being quasi linear time, I had to look up log * n because I never saw this before.
- pfdietz 7y agoAnd then there's O(n alpha(n)), where alpha(n) is an inverse the Ackermann function, and which grows even more slowly than log* n. The famous union-find algorithm has this complexity.
- MaxBarraclough 7y agoWikipedia link: https://en.wikipedia.org/wiki/Log-star https://en.wikipedia.org/wiki/Log-star