Growth

x_max Compress y-axis

Math

The plot above compares a number of well known growth functions. There are various ways to grow and the differences can be quite dramatic and not always intuitive. For instance, given only say 20 COVID-19 cases in January one might only expect linear growth, 40 in february, 80 in march, what we had was exponential growth, which grows as: 10, 100, 1,000, ... , 1,000,000, ....

Logarithmic scale

One can plot log, linear or quadratic curves quite since they do not grow so quickely. However the others grow so fast, that even for very small values of x, the corresponding y value is off the graph. A logarithmic_scale on the y-axis is used compresses the range to y so they can be seen.

With a logarithmic scale one can see that factorial growth has ultimately the highest growth rate followed by exponential.

The plot above is a semi-log plot, the x-axis in linear and the y-axis is logarithmic (on a log-log plot both axes are logarithmic). The exponential curve is a straight line on a semi-log plot because the exponential is the inverse function of the logarithm.

Logarithm

Decimal numbers are an example of logarithmic growth, a billion is just six more zeroes than a thousand. Logarithmic growth grows forever but very slowly. 1000 is 900 more than 100 but only adds a single zero, one million is 900, 000 times more than 100,000 but again we just add another zero.

Polynomial

Linear, quadratic and cubic growth are examples of polynomial growth. This is related to a fundamental problem in computer science, NP-completeness, Problems P can be solved in polynomial time, which means they only grow at the rate of a polynomial function. Problems that can be verified (not necessarily solved) in polynomial time are refered to as nondeterministic polynomial (NP) problems. The question (P=NP?) is, can all NP problems also be solved in polynomial time?

A power law $x^k$ is a straight line on a log-log plot. In a power law the exponent is constant ... Power law:$y=x^{constant}$

Fibonacci growth

Fibonacci is described in detail below.

It grows as $\phi^n$ where $\phi= 1.61803399...$ is the golden ratio.

Exponential growth

Exponential:$y={constant}^x$.

Cumulative interest is an example of exponential growth, where one gets interest on the interest. Half-lives of radio active decay are examples of exponential decay.

The story goes that a king asked what reward a person required, to which he asked for rice, a grain of rice on the first square of a chess board, two on the second, four on the next and so on to the laughter of the court. It's just that would imply 2⁶⁴ grains on the last square.

One grain of rice: $0.029 grams: $$0.029 * 2^{64} = 534,955,578,138\ \text{tonnes}$$

Exponential growth gets big quick.

Factorial

There are n factorial ways of arranging n distinct objects, the growth rate is dramatic, ten factorial is over ten million: $$2!=2 \implies { ab, ba }$$ $$3!=6 \implies { abc, bac, acb, cab, cba, bca }$$ $$...$$ $$10! = 3628800$$ $$14! = 87178291200$$ The factorial is a function of discrete natural numbers, the gamma function is an extension of the factorial for continuous real numbers. $$\Gamma(n) = (n-1)!$$

O notation

The order of a function is it's growth rate. Big-O notation characterizes or classifies functions accordingly.

$$O(log(n)) \lt O(n) \lt O(n^2) \lt O(n^3) \lt O(e^n) \lt O(n!)$$

$f \in O(g)$ means f grows the same as or slower (no faster) than g whereas $f \in o(g)$ means f grows strictly slower than g. So big-O is like ≤ and little-o is like <.

$$\lim_{x\to a} \frac{f(x)}{g(x)} = 0 \implies f(n)\in o(g(n))$$

Quadratic

y =

x₁={{ round2(x1) }} x₂={{ round2(x2) }}

a b c x_max

Quadratic formula

y = ax² + bx + c, a≠0

The roots are where $y$ crosses the x-axis, $y=0=ax^2+bx+c = (x-x_1)(x-x_2)$, the points $(x_1,0)$ and $(x_2,0)$, which can be found using the quadratic formula:
\[x_1,x_2 = {-b \pm \sqrt{b^2-4ac} \over 2a}.\]
The traditional proof is quite hard to remember, an easier one is given here: $$\begin{eqnarray} y &= x^2 + bx + c = (x-x_1)(x-x_2) = x^2 -(x_1+x_2)x + x_1 x_2 \end{eqnarray}$$ This implies that $b=-(x_1+x_2)$ and $c=x_1 x_2$ and the average of the two roots $x_1$ and $x_2$ must be $-\frac{b}{2}$. If this is the average, the midpoint between the two roots, then the two roots must be the same distance $z$ from the midpoint, so $x_1, x_2 = -\frac{b}{2} \pm z$. Since $c =x_1 x_2$ then: $$\begin{eqnarray} c &= x_1 x_2 = (-\frac{b}{2} - z)(-\frac{b}{2} + z) = (-\frac{b}{2})^2 - z^2 \\ \end{eqnarray}$$ $$z = \pm\sqrt{\frac{b^2}{4} - c}$$ \[x_1,x_2 = {-b \pm \sqrt{b^2-4c}}.\]

Cubic y=ax³+bx²+cx+d

y =

x₁={{ }} x₂={{ }} x₃={{ }}

a b c d x_max

Logistic Growth

Midpoint (x₀) Max value (L) Growth rate/Steepness (k) Max x

Math

The logistic map is a sigmoid or S shaped curve. It can be used to model growth of phenomenon that start off growing approximately exponential, then linear then level out at maturity.

Fibonacci growth

Many natural phenomenon grow according to the Fibonacci sequence ... A fibonacci number is simply the sum of it's two predecessors: $$F_0 = 0, F_1 = 1, F{n} = F_{n-1} + F_{n-2}$$

{{ fibonacci(nn) }} ...

This is related to the golden ratio $\phi=1.61803399...$ which has the property:

$$\phi = 1 + \frac{1}{\phi}$$

Rearrange as a quadratic equation: $$\phi^2 = \phi + 1$$ $$\phi^2 - \phi - 1 = 0$$

TODO check

$$x_{roots} = \frac{1 \pm \sqrt{1-4(1)(-1)}}{2(1)} = \frac{1 \pm \sqrt{5}}{2}$$ $$= {{ (1+SQRTROOT5)/2 }}, {{ (1-SQRTROOT5)/2 }}$$ ...

The fibonacci sequence formula is a recurrence relationship, rearrange: $$F{n} = F_{n-1} + F_{n-2}$$ $$F{n_2} = F_{n} - F_{n-1}$$ $$f^2 = f^1 - f^0$$ $$\therefore f^2 - f - 1 = 0$$ This is the characteristic polynomial of the of the fibonacci sequence with roots given above as $\pm \phi$.

...

As an interview question

Writing a program to generate the fibonacci series is a common interview question. One can solve it iteratively, recursively and also closed form solution:

$$f_n = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n\sqrt{5}}$$ ...

Convergence to golden ratio

The ratio of successive Fibonacci numbers quickly converges to the golden ratio $\phi=1.61803399...$:

n F_n F_n+1/F_n
{{ nn }} {{ fibonacci(nn) }} {{ fibonacci(nn+1)/fibonacci(nn) }}