Growth of Functions

How do we compare the speed of an algorithm, the spread of a species, or the expansion of the universe? While these phenomena seem worlds apart, they share a common underlying question: How do they scale? The mathematical concept of the 'growth of functions' provides a universal language to answer this question, offering a powerful lens to analyze and predict the long-term behavior of complex systems. This article bridges the gap between abstract mathematical theory and its profound real-world implications. We will first delve into the "Principles and Mechanisms" of function growth, establishing a clear hierarchy and exploring the tools used to compare different rates of change, from the computational to the purely abstract. Following this, the "Applications and Interdisciplinary Connections" chapter will showcase how this framework unifies our understanding of diverse fields, revealing the deep structural similarities between biological populations, computational complexity, and even the fabric of the cosmos. Let's begin by handicapping this grand race of functions and understanding the rules that govern their competition.

Imagine you are at the starting line of a grand race. The competitors are not athletes, but mathematical functions. Some, like $f(n) = \ln n$, amble along at a leisurely pace. Others, like $g(n) = n^2$, jog steadily. And then there are the sprinters, like $h(n) = 2^n$, which explode forward with astonishing speed. Understanding the "growth of functions" is the art of handicapping this race; it's about predicting, with mathematical certainty, who will win in the long run. This isn't just an abstract game. The running time of computer algorithms, the spread of a pandemic, the expansion of a system's complexity—all these are races run by functions.

At first glance, comparing functions can seem like a dizzying task. Which is ultimately larger: $n^{1.01}$ or $n (\ln n)^2$? How about $n!$ versus $n^n$? To bring order to this chaos, we group functions into families based on their characteristic speed. This creates a clear hierarchy of growth.

The slowest common functions are ​​logarithmic​​, like $\ln n$. They grow, but with extreme reluctance. Then come the ​​polynomial​​ functions, of the form $n^d$ for some constant $d$. These are the workhorses of the world, describing everything from the area of a square ($n^2$) to more complex relationships. Faster still are the ​​exponential​​ functions, like $c^n$ for some constant $c>1$. They represent explosive growth, like the number of ancestors you have as you go back generations.

A fundamental rule of thumb emerges: for large enough $n$, any exponential function will eventually outgrow any polynomial function, which in turn will outgrow any logarithmic function. We can write this informally as:

$\text{logarithms} \ll \text{polynomials} \ll \text{exponentials}$

So, to settle one of our earlier questions, we can be certain that $1.01^n$ (an exponential) will eventually become vastly larger than $n^{1.01}$ (a polynomial). Similarly, the function $n(\ln n)^2$ will eventually surpass the function $n \ln n$.

But what about comparing functions within the same family, or even more exotic creatures like $g_3(n) = n^{\sqrt{n}}$ and $g_5(n) = (\ln n)^n$? A clever trick, almost like putting on a special pair of glasses, is to stop looking at the functions themselves and instead compare their logarithms. If $\ln f(n)$ grows much faster than $\ln g(n)$, it's a very strong indication that $f(n)$ will grow much faster than $g(n)$. Let's try it on our contestants from a hypothetical algorithm analysis:

• $\ln(g_3(n)) = \ln(n^{\sqrt{n}}) = \sqrt{n} \ln n$
• $\ln(g_5(n)) = \ln((\ln n)^n) = n \ln(\ln n)$

Even though $\sqrt{n}$ grows to infinity, the factor of $n$ in the second expression is far more powerful. Since $n \ln(\ln n)$ grows much faster than $\sqrt{n} \ln n$, we can confidently declare that $(\ln n)^n$ is the faster-growing function. This powerful technique of changing our viewpoint allows us to rank a whole menagerie of functions, from the plodding $n^{100}(\ln n)^3$ to the mind-bogglingly fast $n!$, establishing a clear pecking order in the great race.

Knowing who wins the race is one thing, but why do they win? What is the engine driving their growth? Consider a signal processing unit that combines two signals, $g_1(t) = (t^3 + 2t^2) e^{4t}$ and $g_2(t) = 8\sinh(4.5t)$. The hyperbolic sine function, $\sinh(x)$, is really just a combination of exponentials: $\frac{e^x - e^{-x}}{2}$. So, our second signal is essentially $g_2(t) \approx 4e^{4.5t}$ for large $t$. The total signal is their sum, $G(t) = g_1(t) + g_2(t)$. Although $g_1(t)$ has a polynomial part that grows, its exponential engine runs on $e^{4t}$. The engine of $g_2(t)$ runs on $e^{4.5t}$. Just as a race car pulling a bicycle moves at the speed of the race car, the combined signal $G(t)$ will grow at the rate of its fastest component. The ​​asymptotic growth​​ is entirely dominated by the $e^{4.5t}$ term, and we say the ​​growth order​​ of the function is $4.5$.

To get an even deeper insight, we can look at the rate of growth in a way that would make a stock market analyst proud: the ​​instantaneous relative growth rate​​. This is defined as $\frac{f'(n)}{f(n)}$, which is simply the derivative of $\ln(f(n))$. It tells us the percentage gain at any given moment. Let's compare a polynomial, $P(n) = C n^d$, with a superpolynomial function, $F(n) = A \exp(B n^\beta)$ where $0 < \beta < 1$.

• For the polynomial $P(n)$, the relative growth rate is $\frac{P'(n)}{P(n)} = \frac{d}{n}$.
• For the superpolynomial function $F(n)$, the relative growth rate is $\frac{F'(n)}{F(n)} = B \beta n^{\beta-1}$.

Notice something crucial. For the polynomial, the relative growth rate shrinks like $\frac{1}{n}$. For our superpolynomial function, since $\beta < 1$, the exponent $\beta-1$ is a negative number between $-1$ and $0$ (e.g., if $\beta=1/2$, the rate shrinks like $n^{-1/2} = \frac{1}{\sqrt{n}}$). And since $\frac{1}{\sqrt{n}}$ goes to zero slower than $\frac{1}{n}$, the superpolynomial function maintains a higher relative growth for longer. Its engine, while perhaps sputtering, loses power far more slowly than the polynomial's. This subtle but persistent advantage in relative growth is the secret that guarantees it will eventually overtake any polynomial, no matter how large the polynomial's degree $d$ might be.

Here we take a leap of imagination. The idea of "growth" is so powerful that it's not confined to functions of numbers. We can use it to measure the "size" or "complexity" of abstract structures like mathematical groups. A group is a set of elements with an operation, like the integers with addition. In ​​geometric group theory​​, we think of a group generated by a finite set of "moves" $S$. The ​​growth function​​, $\gamma_S(n)$, counts how many distinct elements you can reach using at most $n$ moves.

Let's compare two simple-sounding groups, each generated by two forward moves and their inverses.

1. ​​The Free Abelian Group $\mathbb{Z}^2$:​​ This is the group of movements on an infinite city grid. The generators are "go one block North, South, East, or West". An element is a coordinate $(i, j)$. The key property here is that the moves commute: going East then North gets you to the same place as going North then East. The number of points you can reach in $n$ steps is the number of points inside a diamond shape on the grid. This area grows like a polynomial: $\gamma(n) = 2n^2 + 2n + 1$. This is called ​​polynomial growth​​. It's tame and predictable.

2. ​​The Free Group $F_2$:​​ Imagine navigating an infinite tree, where every turn takes you down a new branch that never, ever loops back. The generators are 'a', 'b', and their inverses. Here, the moves do not commute: move 'a' then move 'b' is a different element from 'b' then 'a'. From the starting point, you have 4 choices. From there, for each next step, you have 3 choices (any move except the one that takes you straight back). The number of elements you can reach explodes exponentially: $\gamma(n) = 2 \cdot 3^n - 1$. This is ​​exponential growth​​.

This distinction is profound. The lack of constraints (non-commutativity) in the free group allows for an explosion of complexity. The constraints of the abelian group (commutativity) tame its growth to be merely polynomial. This simple numerical property—whether the growth is polynomial or exponential—reveals a deep truth about the group's fundamental algebraic structure. It separates "well-behaved" groups, like the group of the Klein bottle which also has polynomial growth, from "wild," complex ones.

Let's bring this powerful perspective back to the world of functions, this time in the complex plane. A well-behaved function on the entire complex plane is called an ​​entire function​​. These functions are incredibly rigid; their behavior everywhere is deeply connected to specific features, like where they equal zero.

A stunning result by the mathematician Jacques Hadamard gives us a deep connection between a function's growth and its zeros. Imagine the graph of a function as a giant, infinite tent stretching over the complex plane. The places where the function is zero are like poles holding the tent fabric down to the ground. Hadamard's theorem tells us something amazing about this tent.

• We can measure the overall ​​order of growth​​, $\rho$, of the function. This is like measuring how fast the tent's ceiling rises as you move away from the center.
• We can also measure the density of the zeros. The ​​exponent of convergence​​, $\lambda$, tells us how "densely packed" the poles are. If $\sum \frac{1}{|a_n|^\alpha}$ converges, where the $a_n$ are the locations of the zeros, it means the zeros are sparse enough. $\lambda$ is the critical value of $\alpha$ where the sum switches from diverging to converging.

The theorem's punchline is a statement of beautiful unity: for a function built purely from its zeros (a "canonical product"), the order of growth is equal to the exponent of convergence of its zeros.

​​$\rho = \lambda$​​

In other words, the growth of the function is dictated by the density of its zeros. A function can't grow very fast if it's pinned down by too many zeros, and a function that grows very quickly cannot have its zeros too densely packed. For example, a function whose zeros are at $\pm i n^{3/2}$ has an exponent of convergence $\lambda = 2/3$, and so its order of growth is also $\rho = 2/3$. More generally, the growth of any entire function comes from two sources: a part determined by its zeros, and a pure exponential part. The overall order of growth is simply the maximum of the two. This principle reveals a profound "anatomical" connection: you can understand a function's global behavior (its growth) by studying its "skeleton" (the pattern of its zeros), or even its "DNA" (the coefficients of its power series).

We have seen that growth rates are essential for classifying algorithms, physical systems, and even abstract algebra. But can any function we write down serve as a useful measure? In complexity theory, we need a measuring stick that we can actually build. A function $t(n)$ is ​​time-constructible​​ if we can build a machine that is guaranteed to stop in exactly $t(n)$ steps on an input of size $n$.

Now, consider a function deviously designed to probe the very limits of what is knowable:

Could this function be time-constructible? Suppose it were. That means we could build a machine that computes $f(n)$ in some number of steps. Once we have the value of $f(n)$, we just check if it's equal to $n^2$ or $n^3$. If it's $n^2$, we know the $n$-th program halts. If it's $n^3$, we know it runs forever. But this would mean we have solved the infamous Halting Problem—a problem Alan Turing proved to be undecidable!

The conclusion is inescapable. The function $f(n)$ is ​​uncomputable​​. You cannot write a program that will reliably calculate its value for any given $n$. And if you cannot even compute the number $f(n)$, you certainly cannot build a machine that runs for exactly $f(n)$ steps. Therefore, $f(n)$ is not time-constructible. This reveals a profound boundary. The mathematical universe of functions is filled with growth rates of unimaginable structure, but the universe of physically realizable computations is smaller. Some "speeds" are not just unreachable; they are fundamentally unknowable. The study of growth doesn't just measure what is; it illuminates the very border of what can be.

In our previous discussion, we explored the formal machinery of function growth—the various notations and classes we use to categorize how quantities change. You might be tempted to think this is a dry, abstract exercise for mathematicians. Nothing could be further from the truth. The study of how functions grow is one of the most powerful and unifying conceptual tools we have. It is a universal language that allows us to find deep, surprising connections between the bustling life in a petri dish, the silent logic of a computer chip, and the majestic expansion of the cosmos. It is the language we use to tell the story of change, of scale, and of complexity. Now, let us embark on a journey to see this language in action, to witness its "poetry" as it describes the world around us.

Perhaps the most natural place to start is with life itself. At its core, life is about growth and reproduction. A population of bacteria, a forest of trees, or even the human species—their fate is written in the mathematics of their growth.

Imagine a small population of organisms in an environment with limited resources. At first, with plenty of food and space, they multiply freely. But as their numbers increase, they begin to compete with one another. The population’s growth slows down. How can we capture this simple story? We can describe the per capita growth rate—the growth rate per individual—as a function of the total population size, $N$. In the simplest, yet remarkably effective, logistic model, this function, $g(N)$, is just a straight line that goes down: $g(N) = r - (r/K)N$. Don't be fooled by the simplicity of this equation. Its two parameters tell a profound biological story. The intercept, $r$, is the growth rate when the population is sparse and free from crowding—it is a measure of the species' intrinsic vitality. The slope, $-r/K$, quantifies how fiercely individuals compete with each other; it is the strength of the system's self-regulation, set by the environment's carrying capacity, $K$. A simple linear function thus elegantly encodes the balance between unchecked proliferation and the harsh reality of limits.

But nature is rarely so simple. What if individuals in a group actually help each other? A pack of wolves is more successful at hunting than a lone wolf; a grove of trees can better withstand the wind. In these cases, the per capita growth rate might initially increase with population density before it starts to fall. This is known as an Allee effect, and to describe it, our simple linear growth function is no longer enough. We need something more complex, perhaps a parabola, which leads to the overall population growth rate behaving like a cubic function of $N$. This seemingly small change—from a linear to a quadratic per capita growth function—has dramatic consequences. It can create a critical population threshold. Fall below this number, and the population is doomed to extinction; stay above it, and it thrives towards its carrying capacity. The system now has two possible destinies (extinction or persistence), a phenomenon called bistability. The entire fate of the species is dictated by the shape of its growth function. This is not just an academic curiosity; understanding this shape is a matter of life and death in conservation biology and fisheries management. The maximum of the growth function, for instance, tells us the maximum sustainable yield—the greatest number of fish we can harvest without crashing the population.

Where do these growth functions ultimately come from? They are not abstract laws handed down from on high; they are emergent properties that arise from the intricate machinery of life at the molecular level. Modern synthetic biology allows us to see this with stunning clarity. Imagine an engineered bacterium where we have modified its genetic code. Each modification might introduce a tiny probability of an error, $\epsilon$, during protein synthesis, or a small time delay, $\beta$, in the production line. A single protein might have $n$ such modifications. The probability of producing a functional protein might decrease exponentially with $n$, as $(1-\epsilon)^n$. The rate of production might decrease as $1/(1+\beta n)$. The cell's overall growth rate, $\mu$, which depends on having enough of this functional protein, becomes a composite function built from these microscopic details: $\mu(n) = \mu_0 \frac{(1-\epsilon)^n}{1+\beta n}$. Here we see a beautiful synthesis: the cell’s growth, its macroscopic behavior, is described by a function whose very form is dictated by the physics and chemistry of its innermost components. We can literally build a growth function from the ground up.

The language of growth is just as crucial for describing the artificial worlds we build inside our computers. Whenever we write a program to solve a problem, a critical question is: "How will it perform as the problem gets bigger?" In other words, how does the computation time grow as a function of the input size, $N$?

Consider the grand challenge of simulating the behavior of materials, from a drop of water to a new type of alloy. A computer does this by calculating the forces between every atom. A naive program might check the force between every possible pair of atoms. If there are $N$ atoms, there are about $N^2/2$ pairs. The runtime of such a simulation grows quadratically, as $\mathcal{O}(N^2)$. This might be fine for a few hundred atoms, but for the millions or billions of atoms needed to model realistic systems, a quadratic growth rate is a death sentence. The calculation would take longer than the age of the universe. The breakthrough comes from a clever physical insight: forces are typically short-ranged. An atom only feels its immediate neighbors. By designing algorithms like cell lists, which cleverly partition space so that we only check nearby pairs, we can change the growth function. The computational cost is transformed from a crippling quadratic to a manageable linear function, $\mathcal{O}(N)$. Understanding the growth function of an algorithm is the difference between the impossible and the possible; it is the art that makes modern computational science feasible.

This concept of growth even extends to the abstract realm of information and finance. Suppose you have identified a favorable investment opportunity. What fraction, $f$, of your capital should you risk on each go? Risk too little, and your wealth grows slowly. Risk too much, and a string of bad luck could wipe you out. The solution lies in analyzing the long-term growth rate of your capital. This rate can be modeled by a specific function, often involving logarithms, such as $G(f) = p \ln(1+bf) + (1-p) \ln(1-f)$. Your goal is to choose the fraction $f$ that maximizes this growth function. This idea, known as the Kelly criterion, connects the growth of wealth to the mathematics of information. The derivative of the growth function at zero, $G'(0)$, tells you whether the game is even worth playing. A positive derivative means you have an edge, an opportunity for growth.

The power of growth functions reaches one of its pinnacles in the theory of machine learning. How is it that a computer can learn from a limited set of examples and make accurate predictions about data it has never seen before? The key is to control the "expressive power" of the learning algorithm. A model that is too simple will fail to capture the patterns (underfitting), while a model that is too complex will just memorize the training data, noise and all, and fail to generalize (overfitting). The theory of Vapnik and Chervonenkis provides a way to measure this complexity through a combinatorial growth function, often denoted $s(\mathcal{H}, m)$. This function doesn't measure growth over time, but rather the growth in the number of different ways a class of models $\mathcal{H}$ can label a dataset of size $m$. If this function grows polynomially in $m$, the model class is "tame" enough to be learnable. If it grows exponentially, it is too wild, and generalization is impossible. Here, the very possibility of artificial intelligence is tied to the rate of growth of a combinatorial function.

Having seen how growth functions describe life and logic, we now turn to the largest and most abstract canvases: the structure of mathematics and the universe itself.

In pure mathematics, a "group" is a set with a rule for combining elements, capturing the essence of symmetry. We can visualize a group as a vast, infinite network. If we start at one point (the identity element), the group's growth function, $\gamma(n)$, tells us how many new points we can reach within $n$ steps. Different groups have vastly different geometries, which are reflected in their growth rates. The free group on two generators, for instance, feels like exploring an infinite tree that branches out at every step; its number of accessible points grows exponentially. Other groups, corresponding to the familiar flat geometry of a grid, have growth functions that are polynomials. The rate of growth—whether polynomial, exponential, or something in between—is a deep property of the group's structure, a fundamental fingerprint that helps mathematicians classify these abstract universes.

Finally, we look outwards to the grandest scale of all. Our universe began almost 14 billion years ago in a hot, dense state, almost perfectly uniform. The magnificent cosmic web of galaxies, stars, and planets we see today grew from minuscule quantum fluctuations in that primordial soup. The epic story of our cosmos is the story of the growth of structure. Cosmologists model this with a function, $D(a)$, which describes how the density contrast grows as the universe expands (as a function of the scale factor $a$). The logarithmic derivative of this function, $f = \frac{d \ln D}{d \ln a}$, known simply as the growth rate, is one of the most important numbers in cosmology. We cannot watch this growth happen in real time. But we can see its effects. The gravity from a massive galaxy cluster pulls in surrounding matter, and this motion along our line of sight distorts the cluster's apparent shape. A cluster that is truly spherical in space will appear squashed in our telescopes. The amount of squashing depends directly on the growth rate $f$. By meticulously measuring the shapes of countless galaxies, we are reading the history of cosmic growth, and in doing so, we are probing the very nature of the dark matter and dark energy that govern the universe's ultimate fate.

From the microscopic struggle for survival to the expansion of the cosmos, from the efficiency of an algorithm to the essence of learning, the concept of a function's growth provides a unifying thread. It teaches us that to understand a system, we must ask: How does it scale? The answer, written in the universal language of mathematics, reveals the fundamental principles that shape our world and our knowledge of it.