Knuth–Morris–Pratt algorithm: Difference between revisions

Content deleted Content added
thus is confusing. the space complexity W is not that because of the time complexity being W it is that because the array is size W
Line 428:
===Efficiency of the table-building algorithm===
 
The time (and thus space) complexity of the table algorithm is <math>O(k)</math>, where <math>k</math> is the length of <code>W</code>.
 
* The outer loop: <code>pos</code> is initialized to 1, the loop condition is <code>pos < k</code>, and <code>pos</code> is increased by 1 in every iteration of the loop. Thus the loop will take <math>k - 1</math> iterations.