Different Growth Rates

[OHAD]

So, before I'll start- Can anyone tell me the exact defenition of a Growth Rate for Infinite-growing patterns?
I know that speed for a certain pattern (mostly spaceships) is simply a fraction that represents the movement as a number of cells, divided by the number of generations it takes for the pattern to move/spread to that distance. It's a simple physics equation-distance/time=speed.
But, as for infinitely-growing patterns.. I get confused.
Does the growth rate represents the growth in the bounding box of the pattern, or by the population (number of cells according to number of generations)? It seems like both of those are wrong.

In the bounding box growth method, some of the simpler infinite-growing patterns (like the Gospar Glider Gun) will actually have an extremely big growth rate- For the Gospar Gun, the bounding box increases every 4 generations! But, it isn't the story. They have the smallest growth rate (linear).
In the population growth method, "Max" and other space-fillers releated to him will have a growth rate which is much, much bigger than the others. They do have a big growth rate in the real method, but they have the same rate as Space Rake, for an example. It's not the same growth rate in population- While Space Rake gets bigger population once per, about, 4 generations- Max gets a population of 1000000 in a few thousands generations.

I can't seem to find any other methods to calculate the growth rate, so can someone give me the exact defenition?

Thanks

[velcrorex]

Growth rate is determined by population. Try making a graph of population vs # of generations; basically the shape of the graph determines the growth rate as the number of generations gets bigger. If the graph looks like a line (with a positive slope) then the growth is linear. Quadratic growth will look like a quadratic equation, and logarithmic growth will look like the plot of a logarithmic function. Remember, this is the behavior of the population as the number of generations increases.

Some of the different growth rates and corresponding patterns can be found here:
http://conwaylife.com/wiki/Infinite_growth#Growth_rates

[dvgrn]

Growth rate is determined by population.

There are relatively few exceptions to this, but there are some patterns designed to have a particular growth rate in length or area, where population is relatively unimportant. An example is logarithmic-width.mc in Golly's Patterns/Hashlife folder... also Calcyman's O(sqrt(log(t))) 2D binary counter (which I have to find a copy of somewhere again.)

Population and area are generally related in some way, of course. For example, the 2D binary counter's population grows in proportion to log(t) -- in a "sawtooth" way, since it drops back to the same minimum population periodically, at longer and longer intervals as the area increases. The area also grows in proportion to log(t), but naturally that means the diameter grows at O(sqrt(log(t))), the slowest possible rate for an unbounded-growth Life pattern -- and that's the growth rate for which that pattern was designed.

I can't seem to find any other methods to calculate the growth rate, so can someone give me the exact defnition?

One good resource to look at is Dean Hickerson's Life pages -- there's a section titled "Unusual Growth Rates", and the linked patterns have very good detailed annotations, mostly related to population growth rates. If you can follow through a few of those notes and see how they apply to the pattern, you'll have made a good start on understanding how these calculations work.

In general, the rate being calculated is the limit rate as t approaches infinity. This means you can basically discard any constant or lower-order terms in the calculation -- a huge initial pattern and a tiny one can easily have the same growth rate. A spacefiller at T=0 and the same spacefiller at T=1,000,000, for example, will have very different starting populations, but the growth-rate calculation will come out the same.

... I hope I haven't said anything above that's too mathematically inexact -- I'm intermittently allergic to big-O notation [Wikipedia], so sometimes I slip up a bit. If you have similar allergies, I do still recommend checking out the Wikipedia link above, but skip the "Formal Definition" and go straight to the "Example" and "Usage" sections. The basic idea is really fairly simple, but they sure do make it look complicated!

[MikeP]

For the Gospar Gun, the bounding box increases every 4 generations! But, it isn't the story. They have the smallest growth rate (linear).

A picture is worth a thousand words ... so here's a quick picture of a couple of different growth rates:



This is why quadratic growth is considered to be faster: the pattern with quadratic growth may start off more slowly, but it catches up with the linear pattern and overtakes it eventually.

In fact any quadratic growth pattern will eventually overtake any linear growth pattern, no matter how badly it seems to be doing at first - though this might not happen for a long time.

This is why we talk about behaviour "in the limit, as t approaches infinity". We're referring to how a pattern behaves for the whole of infinite time. The quadratic growth pattern may be smaller for a finite time at the start of its evolution, but this is trivial compared to the infinity of generations later on where it's in the lead.