What actually growth of a function represents? I am going through the book Discrete Mathematics by Kenneth Rosen. In chapter 3, there is a topic "The Growth of Functions" and then Big-O Notation. I am really unable to understand what actually Growth of Functions represents? Kindly share some insights with examples. That would be of great help. Thank you so much for the help.
PS: I am new to this topic.
 A: Not sure if you have a specific question, but it seems you understand big O notation but want some input on its significance. Broadly speaking, I would say it gives us a way to understand the behavior of something complicated or less familiar in terms of something simple and more familiar, particularly as an input size grows.
For instance, consider the function
$$f(n)=9\log n +2\sin n +3(\log n)^2-n^2+n^3.$$
While this function is elementary, its expression is a bit messy. Moreover, perhaps we are not interested in its precise expression. Perhaps we simply want to know its behavior for large $n$.  Intuitively, we know the $n^3$ term dominates the expression. Big O notation formalizes this intuition:
$$f(n)=O(n^3)\text{ as }n\uparrow \infty $$
so we can say $f$ behaves "like $n^3$" (has order of $n^3$) for $n$ large. This is a more simple and palatable characterization of $f$ than its full functional form.

The above example was a warm up where the function $f$ had a closed form, but there are several applications where characterizing the growth of a function is particularly useful because we simply don't have a closed form expression for it. I will briefly describe a couple applications that come to mind:
i. Number theoretic results can be usefully stated using big O notation. For instance, there is no known efficiently computable formula for the exact sequence of prime gaps (the difference between consecutive prime numbers). Still, we can state important results about the long-run size of these gaps. For instance, the best known unconditional bound on the size of gaps is
$$p_{n+1}-p_n=O(p_n^{0.525}),$$ where $p_n$ is the $n$th prime number.
It turns out that the Riemann hypothesis implies slightly smaller gaps of
$$p_{n+1}-p_n=O(\sqrt {p_n} \log p_n).$$ However, Cramer's conjecture, which is based on a probabilistic model of prime numbers, asserts that the gaps are even sharper:
$$p_{n+1}-p_n=O( (\log p_n)^2).$$
ii. Another application is in algorithms. An algorithm is a finite sequence of instructions, but may not have a clean functional form. Characterizing the runtime of an algorithm using big O notation thus gives a useful snapshot metric of its performance, and its quantitative nature allows one to compare the performances between different algorithms (i.e. it measures their efficiency).
For instance, consider solving the travelling salesman problem (TSP), which asks for the shortest route that visits every city on a map exactly once and returns to the origin, given a list of $n$ cities and distances between them. A natural question to ask about an algorithm that solves it is: How many elementary operations does it take solve TSP, particularly when the number of cities, $n$, is large?
A brute force algorithm that checks all permutations on the map gives an exact solution and takes factorial time, i.e. it is $O(n!).$ This means the number of elementary operations needed to solve the problem by brute force grows superexponentially as you add more cities.
However, the Held–Karp algorithm, an approach based on dynamic programming, also gives an exact solution but has runtime $O(n^2 2^n),$ which is much better than factorial time (it only takes exponential time). We can make such quantitative comparisons between algorithms by studying the growth of their runtime with the help of big O notation.
Wiki has a nice table of time complexities with some example algorithms that you may find of interest. Time complexity is certainly a fascinating topic for further reading if you are interested in algorithms.
A: Instead of the Big-O notation I'll focus more on the broader concept of growth for functions. As a disclaimer, what I mention below is not quite the Big-O notation, but more like comparability, so the Big-O notation applied both ways. Let's say that two functions $f$ and $g$ are comparable if $f=O(g)$ and $g=O(f)$ (this is the same thing as the "order" of the function as defined in the book you cite).

Growth functions can also be associated to geometric objects which admit some notion of size. For instance one can consider the volume $\gamma_d(r)$ of the closed box with sides of length $r$ in $\mathbb{R}^d$ centered at the origin. It is clear that $\lim_{r\to\infty} \gamma_d(r)=\infty$, but $\gamma_1(r)$ escapes to infinity like $r$ does, whereas $\gamma_3(r)$ escapes to infinity as $r^3$ does, and although $r$ and $r^3$ are both of polynomial type, the growths they represent are different (i.e. their growth type is different). So the growth type picks out the dimension of the space in a sense. E.g. if I were to disclose that for some anonymous $d$, $\gamma_d(r)$ is $O(r^{6.5})$ but is not $O(r^5)$, you could determine that $d=6$.

Another application of this idea is to groups. Take a finitely generated group $G$ and fix a generator set $S$. Then for $n$ a nonnegative integer, put $\gamma_{G,S}(n)$ to be the number of elements in $G$ that can be written as the product of $n$ elements that come from $S$ or $S^{-1}=\{s^{-1}\,|\, s\in S\}$. This function depends on $S$ (as well as $G$), however its growth type as $n\to \infty$ does not. As an example, consider $G=\mathbb{Z}^d$ with $S=\{e_1,....,e_d\}$, where the $e_i$ are the standard basis elements, and again $G=\mathbb{Z}^d$ with $S'=S\cup\{2e_1,3e_4\}$. Both $\gamma_{G,S}(n)$ and $\gamma_{G,S'}(n)$ will escape to infinity like $n^d$. So again the growth (type) of a certain function picks out the dimension. Note that this example is not too different from the first example I gave, if one considers the Cayley graph construction (see e.g. Cayley Graph intuition ). Different generating sets produce different Cayley graphs, but the growth of the size of the "ball of radius $n$" in any Cayley graph of a finitely generated group only depends on the group.

In more complicated situations the growth type of such "size functions" also say something about the group or space, though often it's not as straightforward as the rank or dimension of the group/space. For instance the growth function $\gamma_{H,S}(n)$ of the $3\times 3$ Heisenberg group with integer coefficients
$$H=\left\{\left.\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\end{pmatrix}\,\right|\, x,y,z\in \mathbb{Z}\right\}$$
is of type $n^4=n^{1+1+2}$, even though the group has $3$ degrees of freedom. In this case the top right entries grow twice as fast as the other two entries, so in a sense the growth type takes into account the effect of the commutator.

Further, under broad conditions one can associate certain groups to spaces (e.g. one can look at the fundamental group of a Riemannian manifold), and have a variety of size functions simultaneously. One can then relate the growths of these size functions to themselves and to other objects associated to the manifold. For instance, a theorem by Milnor says that if $M$ is a compact manifold with negative sectional curvature, then $\gamma_{\pi_1(M),S}(n)$ grows exponentially in $n$ as $n\to\infty$. (This is in the first reference I cited at https://math.stackexchange.com/a/4283977/169085 .)

Let me finish by mentioning a very important theorem by Gromov (see his paper "Groups of Polynomial Growth and Expanding Maps"): Let $G$ be a finitely generated group with a generator set $S$. Then the growth type of $\gamma_{G,S}(n)$ is polynomial (so $\gamma_{G,S}(n)$ grows like $n^p$ for some $p\in\mathbb{Z}_{\geq0}$) if and only if the group is virtually nilpotent (i.e. $G$ has a finite index subgroup that is nilpotent).
Essentially this means that polynomial growth for finitely generated groups picks out a fundamental structural similarity of the group to $\mathbb{Z}^d$ and $H$.
A: Growth of a particular function is basically how a function would behave for sufficiently large values of the input to function. You particularly ask about the big -O notation. 
Let us say we have two functions $f(x)$ and $g(x)$ and if we say that $f(x)=O(g(x))$ then that means that there exists  numbers $c$ and $n_0$ such that $f(x) \leq c.g(x) \forall x \geq n_0$.
So you basically are saying that for sufficiently large values of $x$ (which is depicted in condition $x\geq n_0$) the function $f(x)$ is below the function $c.g(x)$ for all further values. In a way you are predicting the behaviour of the function in terms of another function. Basically you are setting an upper bound for the function $f(x)$ in terms of $g(x)$.
For example let's take $f(x)=x$ and $g(x)=x^2$. Now, note that for all $x \geq 1$, $f(x)\leq 1.g(x)$. So, in this example you get $c=1 , n_0=1$. 
Note that $g(x)$ is indeed an upper bound but this upper bound is not tight. And you can get a better approximation.
So, generally when we talk about growth of functions we are interested in a very tight bound. 
There are many places where you can't exactly pinpoint the value of a function so you give a big - O bound for that function. For example, the great prime number theorem gives us the estimate of the number of primes up till a given number uses this notation.\
