Content deleted Content added
→Runtime: It is given in the code for manachers algo that "while Center < length(S')" that is less than 2n+1 not less than equal. I changed 2n+1 to 2n to correct it. Tags: Reverted Visual edit |
→Runtime: i am taking back my previous edit of 2n+1 -> 2n as after center becomes 2n it will be incremented one last time inside the loop before being rejected by the while loop for being not less than 2n+1. |
||
Line 166:
===Runtime===
The algorithm runs in linear time. This can be seen by noting that <code>Center</code> strictly increases after each outer loop and the sum <code>Center + Radius</code> is non-decreasing. Moreover, the number of operations in the first inner loop is linear in the increase of the sum <code>Center + Radius</code> while the number of operations in the second inner loop is linear in the increase of <code>Center</code>. Since <code>Center ≤ 2n+1</code> and <code>Radius ≤ n</code>, the total number of operations in the first and second inner loops is <math>O(n)</math> and the total number of operations in the outer loop, other than those in the inner loops, is also <math>O(n)</math>. The overall running time is therefore <math>O(n)</math>.
==Notes==
| |||