Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16153

Re: Another little puzzle

Show all headers | View raw

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> 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...)

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-21 13:17 -0800
  Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-22 04:10 +0000
    Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-24 06:21 -0800
      Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-24 16:53 +0000
        Re: Another little puzzle Richard Heathfield <rjh@cpax.org.uk> - 2022-12-24 17:14 +0000
        Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-24 22:30 +0000
          Re: Another little puzzle Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-25 00:02 +0000
            Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 01:30 +0000
            Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 01:55 +0000
        Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 00:37 -0800
      Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 00:41 +0000
        Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 01:05 -0800
          Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 09:30 -0800
          Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-25 21:44 +0000
            Re: Another little puzzle Richard Damon <Richard@Damon-Family.org> - 2022-12-25 17:59 -0500
              Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 18:39 -0800
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-26 03:18 +0000
            Re: Another little puzzle Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-25 18:35 -0800
              Re: Another little puzzle Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-26 03:49 +0000

csiph-web