Path: csiph.com!news.mixmin.net!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.programming Subject: Re: Another little puzzle Date: Sun, 25 Dec 2022 09:30:55 -0800 Organization: A noiseless patient Spider Lines: 36 Message-ID: <86fsd3xueo.fsf@linuxsc.com> References: <86pmcczcak.fsf@linuxsc.com> <87wn6krsc5.fsf@bsb.me.uk> <868riwzxu3.fsf@linuxsc.com> <87y1qwpb5p.fsf@bsb.me.uk> <86mt7byhtp.fsf@linuxsc.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader01.eternal-september.org; posting-host="bacb00f09a0305cdb2c72c0e332a04cb"; logging-data="2958011"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18jQW+xfNEiGWYekvA1Lx8wRgQNc8NlkNc=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:Fb6XBJ3Hbiqh73khSUjIdWHbE1U= sha1:dysBEVd40MPJ6jHaqGGFrs5F/dk= Xref: csiph.com comp.programming:16153 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...)