Skip to content

Commit 0d54cff

Browse files
lrvideckisadamant-pwn
authored andcommitted
nitpick - It feels weird reading "sort" followed by "O(n)"
1 parent 5360c45 commit 0d54cff

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

src/string/suffix-array.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -201,7 +201,7 @@ We use temporary arrays $pn[]$ and $cn[]$ to store the permutation by the second
201201
}
202202
```
203203
The algorithm requires $O(n \log n)$ time and $O(n)$ memory.
204-
However if we take the size of the alphabet $k$ into account, then it uses $O(n \log n + k)$ time and $O(n + k)$ memory. The first sort takes $O(k)$ time, but all following sorts are bounded by the number of equivalence classes, and take $O(n)$ time.
204+
However if we take the size of the alphabet $k$ into account, then it uses $O(n \log n + k)$ time and $O(n + k)$ memory. The first counting sort takes $O(k)$ time, but all following counting sorts are bounded by the number of equivalence classes, and take $O(n)$ time.
205205
206206
For simplicity we used the complete ASCII range as alphabet.
207207
If we know that the string only contains a subset of characters, e.g. only lowercase letters, then this implementation can obviously be optimized.

0 commit comments

Comments
 (0)