"Julio Di Egidio wrote: >"quasi wrote: >> ols6000 wrote: >>> >>>One further thing to keep in mind: a method in which you select >>>the best of N-1 lines is O(N^2), because calculation of the sum >>>for each line is O(N). That means such a method isn't practical. >> >> Good point. >> >> The most efficient algorithm proposed so far has complexity O(N) >> _times_ the complexity of a distance sum calculation. >> >> However, a distance sum calculation by its very nature is O(N). >> so if each one of the distance sum calculations has to be done >> separately, and if each one is O(N), then, as you indicate, the >> whole task is O(N^2). >> >> It seems unlikely that you can do better. > >As already noted, we can indeed do better, namely O(N+N), as >there is no need to recalculate the cost function from scratch >at each step.
I must have missed that.
If you can avoid recalculations of the cost function at each step, then, as you indicate, the whole task is just O(N), and thus, ols6000 is potentially back in business.