Content deleted Content added
No edit summary |
|||
Line 148:
I restored the simple algorithm presentation to this page on the grounds that other parts of that section refer to it, making the overall page hard to understand if it isn't there. I hate calling other WP users incompetent, but this felt a lot like it; the removalist didn't even try to read the page afterwards to see if it made basic sense! (Whether or not the example should be here is not my concern; the page should at least read as a consistent entity...) --[[User:Dkf11|Donal Fellows]] ([[User talk:Dkf11|talk]]) 22:12, 3 January 2010 (UTC)
==Time complexity of multiple pattern search==
The time complexity initialization stage of the algorithm (lines 3,4) is O(mk).
The reason is that each hash calculation takes O(m) Time and we have k of them.
Thus, the overall time complexity should be O(max(n,mk)).
[[User:Elhanan mishraki|Elhanan mishraki]] ([[User talk:Elhanan mishraki|talk]]) 20:19, 17 May 2011 (UTC)
| |||