|
|
|
|
|
|
by jhdevos
4139 days ago
|
|
|
Wording is a bit sloppy: "Extending R (the inner while loop) takes at most a total of N steps, and positioning and testing each centers take a total of N steps too. Therefore, this algorithm guarantees to finish in at most 2*N steps, giving a linear time solution." What he means is that the total time taken by ALL executions of the inner loop combined is at most N, not that each run of the inner loop takes at most N steps (otherwise it would become quadratic). |
|
|