Re: [Rails-devel] Automatic route calculation

[brett l. <bre...@gm...>]

On Sun, Mar 21, 2010 at 10:54 AM, alexti <al...@sh...> wrote:
> On Sun, 21 Mar 2010 11:44:48 -0600, brett lentz <bre...@gm...>
> wrote:
>
>> http://en.wikipedia.org/wiki/Big_O_notation
>>
>> O(n!) means that for each vertex/edge that's added to the calculation,
>> the time it takes for the algorithm to reach a solution grows by a
>> factorial order of magnitude.
> Brett, O(n!) only describes asymptotic behaviour, it doesn't mean that if
> you go from 1000 to 2000 than your time will increase by 2000!/1000!
> factor. In 18xx games there is also an interesting property of adding an
> edge unconnected to the station does not increase time at all and this is
> not uncommon in many games (at first because the track is not connected
> and later because it is blocked).
>
> Alex.

You're right. Our problem isn't strictly the traveling salesman (which
is usually where O(n!) is seen).  I don't expect your algorithm to be
O(n!), but maybe closer to O(n^2) or O(2n).

---Brett.