4 ms·
The author states that preprocessing takes O(m) time but that is on average. A quick review of the code makes me think that its worst case is actually on the o
by bnoordhuis 16y ago
The author states that preprocessing takes O(m) time but that is on average.
A quick review of the code makes me think that its worst case is actually on the order of O((s * (s + 1)) / 2), where s = m / 2.
The Achilles heel is the hash function. It's trivial to create collisions and have the insertion time for word w turn from O(1) to O(w).
- martincmartin 16y agoUm, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.
- bnoordhuis 16y agoSorry, I updated my comment just as you posted yours. But - and I don't want to sound pedantic - how is m^2 not exponential growth? Edit: mea culpa guys, I carelessly translated from Dutch. You're all right: quadratic, not exponential growth.
- Locke1689 16y agoExponential growth is O(2^m). This is not pedantic -- it's definition. O(m^k) is polynomial, O(k^m) is exponential.
- bigiain 16y agoBecause 2^m and m^2 are very different... Using terminology like "exponential" and "quadratic" correctly in a discussion of algorithms is not pedantic...
- theoretical 16y agox^2 is quadratic, 2^x (for example) is exponential. Have a look at http://en.wikipedia.org/wiki/Time_complexity http://en.wikipedia.org/wiki/Time_complexity , it's pretty comprehensive.
- state_machine 16y agoBecause 2, the exponent in that expression, is a constant. Exponential growth would be 2^m.
- cperciva 16y agohow is m^2 not exponential growth m^2 is exponential -- in the value 2. But the value 2 doesn't change very rapidly, so we tend to focus on the m component of the expression. :-)
- leif 16y agoUniversal hashing will prevent collision problems.
- lvvlvv 16y agoI am the author. You are right. I've updated the page.