Content deleted Content added
→Runtime: Fixed typo. |
Getabyte1432 (talk | contribs) m change "the first loop can run at most <math>n+n/2</math> times." to "the first inner loop can run at most <math>n+n/2</math> times." |
||
Line 110:
===Runtime===
The algorithm runs in linear time. This can be seen by putting bounds on how many iterations are run of each loop. The outer loop and second inner loop increment Center by 1 for every iteration. Since Center is bounded by the length of the string, we know these loops run <math>n</math> times. The first inner loop increments Radius by 1 for every iteration and the second inner loop, when it stops, decrements Radius by at most 1 for every iteration. Since the second loop can run at most <math>n</math> times and the value for Radius cannot exceed <math>n/2</math>, the first inner loop can run at most <math>n+n/2</math> times. The overall runtime is <math>O(n + n + n/2) = O(n)</math>.
==Notes==
| |||