Timeline for Check whether set of strings is prefix-free via lexicographic sort?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 24, 2023 at 15:10 | answer | added | LD50 | timeline score: 1 | |
| Jul 24, 2023 at 13:35 | answer | added | LD50 | timeline score: 1 | |
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Sep 9, 2016 at 20:28 | comment | added | KWillets | Oops, my brain is elsewhere today. N^2 in the second term. | |
| Sep 9, 2016 at 19:53 | comment | added | KWillets | It will be $O(N \log N + N)$ in that case, if you obtain the LCP's during the sort. | |
| Sep 9, 2016 at 18:46 | comment | added | D.W.♦ | This algorithm is correct, but depending on what $N$ is intended to represent, the running time is not $O(N \lg N)$. Consider a set of $N$ strings, where each string starts with $N$ a's. Then the running time is more like $O(N^2 \lg N)$, because comparing a pair of strings takes $O(N)$ time rather than $O(1)$ time. | |
| Sep 9, 2016 at 18:44 | history | edited | D.W.♦ | CC BY-SA 3.0 |
deleted 43 characters in body; edited title
|
| Sep 9, 2016 at 17:18 | vote | accept | Ahmed Fasih | ||
| Sep 9, 2016 at 17:04 | answer | added | KWillets | timeline score: 2 | |
| Sep 9, 2016 at 16:51 | history | edited | Ahmed Fasih | CC BY-SA 3.0 |
speed test
|
| Sep 9, 2016 at 16:12 | history | asked | Ahmed Fasih | CC BY-SA 3.0 |