From: tr.17687@z991.linuxsc.com   
      
   Tim Rentsch  writes:   
      
   > Ben Bacarisse  writes:   
   >   
   >> Tim Rentsch  writes:   
      
   [pulled up from further on in the responded-to posting]   
      
   > [By "conventional average" I mean a time/direction A such that]   
   >   
   >     A that minimizes { Sum_{i=1,n} difference(A, t(i))^2 }   
   >   
   > where 'difference' means the shorter arc length.   
      
   [...]   
      
   >>> The "conventional average" metric can be calculated in O(n*n).   
   >>   
   >> By which I presume you mean and /not/ in O(n).  (Big O is just an   
   >> upper bound.)   
   >   
   > What I mean is I have an algorithm that runs in time proportional   
   > to n*n.  I suspect that there is an algorithm with better big-O   
   > behavior (probably O( n * log n )), but I don't actually have one   
   > to show, so I simply gave the best big-O result that I knew.   
      
   After some further thought I have convinced myself that there is   
   indeed an algorithm that is O( n * log n ).  The idea isn't that   
   complicated, but it's tedious, so I haven't actually implemented   
   it.  Perhaps someone will be interested to take that as a challenge   
   problem.   
      
   And who knows, maybe there is an algorithm with even better big-O   
   performance.  At least for now that's above my pay grade.   
      
   (and of course, Merry Christmas...)   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)