17-Jun-2013 22:02, monarch_dodra пишет:
On Monday, 17 June 2013 at 17:13:49 UTC, Dmitry Olshansky wrote:
And this is all nice and have its place too but I'm mostly talking
about O(N*M) vs O(N).
Well... putting it that way always looks nice on paper, but for what
values of N and M is it actually *faster* ?
Also, are we talking about *actual* O(N), or average case O(N) ? Because
the link has a worst case scenario of O(N*M).
I'm sure I'm reading it right:
- preprocessing phase in O(m) time and constant space complexity;
- constant space complexity for the preprocessing phase;
- searching phase in O(n) time;
- performs 2n-m text character comparisons in the worst case.
--
Dmitry Olshansky
