3 ms·
Can anyone explain to me why this is said to be O(n) when it heavily relies on sorting?
by skrebbel 4y ago
Can anyone explain to me why this is said to be O(n) when it heavily relies on sorting?
- rullelito 4y agoWiki mentions https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array is used for performance.
- Lichtso 4y agoNot only that, the suffix array [1] is using counting sort O(n) instead of a comparison based O(n log n) sort. That is because they assume integer alphabets. For general alphabets they can only achieve O(n log n). [1] https://arxiv.org/abs/1610.08305 https://arxiv.org/abs/1610.08305