4
$\begingroup$

I was wondering if say for increasing functions $f(x),g(x)$ with $f(x)$ asymptotically growing faster, $f(g(x))$ grows faster than $g(f(x))$. As is, I know you cannot say as you can find examples where $f(g(x))$ is faster and examples where $g(f(x))$ is faster, example of latter would be $f(x)=x!$ and $g(x) = 2^x$.

But this really goes against my intuition of "the faster one should be used last". I don't know if this question even makes sense, but is there some point where $f(x)$ is so much faster growing than $g(x)$ that $f(g(x))$ beats out $g(f(x))$?

For example (the following may be wrong), I thought about a function $f(x)$ that grows around the speed of $g^{(x)}(x) = \underbrace{g\circ g\circ \dots \circ g}_{x~~g's}(x)$, and in this case $f(g(x)) \sim g^{g(x)}(g(x))$ whereas $g(f(x)) \sim g^{x+1}(x)$ which is clearly way slower (assuming $g(x)$ grows reasonably fast). Intuitively I feel like if $f(x)$ grew any faster than this, the result should stay the same but I don't know how to go about arguing this in any way.

Essentially, if you are thinking about growth speeds of the compositions, intuitively (at least to me), the growth speeds of the functions you are composing seem to be enough information to decide this. It seems weird that some specifics of the structure or logic of the functions themselves can overturn this.

$\endgroup$
2
  • 1
    $\begingroup$ Assume $f$ and $g$ are strictly increasing. Assume $(f\circ g) > (g\circ f) $ as $x$ goes to $\infty$ . Then $(f\circ g)^{-1}< (g\circ f)^{-1} $ But this translates to $(f^{-1} \circ g^{-1}) > (g^{-1} \circ f^{-1})$ . Yet $(f>g)$ iff $(f^{-1} < g^{-1})$. So, assume there is a correlation between the growth of $f$ relative to $g$ and the growth of their composites. Then the inverse functions $f^{-1}$, $g^{-1}$ will exhibit the opposite correlation. $\endgroup$ Commented Aug 23 at 1:56
  • $\begingroup$ This is interesting, I guess it is pointing to an analogous question of slower and slower (yet still increasing) functions. $\endgroup$ Commented Aug 27 at 5:04

2 Answers 2

Reset to default
2
$\begingroup$

We want to compare the growth rates of $ f(g(x)) $ and $ g(f(x)) $ by differentiating both.

$$ \frac{d}{dx} f(g(x)) = f'(g(x)) g'(x) $$

$$ \frac{d}{dx} g(f(x)) = g'(f(x)) f'(x) $$

To determine which function grows faster, compare:

$$ f'(g(x)) g'(x) \quad \text{vs.} \quad g'(f(x)) f'(x) $$

  • If $ f'(g(x)) g'(x) > g'(f(x)) f'(x) $, then $ f(g(x)) $ grows faster.
  • If $ f'(g(x)) g'(x) < g'(f(x)) f'(x) $, then $ g(f(x)) $ grows faster.

So, while there doesn't exist a universal rule of thumb relating the order of function composition and their growth rates; you can compare the growth rates of any known functions using the derivative test. Hope this helps :D

$\endgroup$
8
  • $\begingroup$ Is there justification that there is not a rule? This is kind of what my question is asking $\endgroup$ Commented Mar 16 at 4:11
  • $\begingroup$ Also the derivative test doesnt even necessarily work, we can define a function that grows in $\Theta(n)$ that has an unbounded derivative for instance $\endgroup$ Commented Mar 16 at 4:24
  • $\begingroup$ There are cases where either composition can dominate: If $ f(x) = x! $ and $ g(x) = 2^x $, then $ f(g(x)) = (2^x)! $ grows much faster than $ g(f(x)) = 2^{x!} $. But if $ f(x) = e^x $ and $ g(x) = x^2 $, then $ g(f(x)) = (e^x)^2 = e^{2x} $ grows faster than $f(g(x)) = e^{x^2}$. $\endgroup$ Commented Mar 16 at 4:25
  • $\begingroup$ I know specific examples, this is not what my question is referring to though $\endgroup$ Commented Mar 16 at 4:25
  • 1
    $\begingroup$ I guess that when $x$ tends to the infinity then $e^{2x}$ grows slower than $e^{x^2}$. $\endgroup$ Commented Aug 23 at 20:08
2
+50
$\begingroup$

EDITED to better address OP's question: Based on the growth rates and structure of the individual functions, the answer can change, and change infinitely often. If $f$ grows rapidly enough and much faster than $g$, then $f(g(x))$ will grow more rapidly than $g(f(x))$. OP gives the example where $f(x)=x^{x^{\ldots^x}}$ with a power tower of height $\lceil x\rceil$ and $g(x)=e^x$. In this case, $f(g(x))$ grows faster than $g(f(x))$. Here is a somewhat more general way to construct examples.

Examples where $f(g(x))$ grows faster than $g(f(x))$.
Suppose $g: [0,\infty)\to [0,\infty)$ is any continuous strictly increasing function such that $g(x)>x$ for $x\geq 0$. We can define the function $f(x)$ using the following formula: $f(g(x))=xg(f(x))^{x}$. Since $g$ is continuous and strictly increasing, $f$ is a well defined function $f:[g(0),\infty)\to [f(g(0)),\infty)$. By definition, $f(g(x))$ grows much faster asymptotically than $g(f(x))$.

Remark: $f$ can be defined recursively on $[0,\infty)$. Initially, let $f(x)=1$ for $x\in [0,g(0))$. For $y\in [g(0),g(g(0)))$, let $x\in [0,g(0))$ be the unique real number such that $g(x)=y$. Define $f(y)=xg(f(x))^x$. Thus, $f(g(x))=x g(f(x))^x$. This procedure can be continued recursively on the intervals $[g^{n}(0),g^{n+1}(0))$ for $n\geq 1$ until $f$ is defined on $[0,\infty)$ and satisfies the formula.

Examples where $g(f(x))$ grows faster than $f(g(x))$.
We can also give a procedure for defining arbitrarily fast growing functions $g$ and $f$ such that $g(f(x))$ grows faster than $f(g(x))$.
Suppose $g(x)$ grows at least exponentially or in particular satisfies the property that $g(xc)\geq \big(g(c)\big)^x$ for $c,x\geq 1$. Also, assume $g(1)>1$. In this case, $g(x)>x$ for $x\geq 1$. If $f(x)=xg(x)$, the function $g(f(x))$ grows more rapidly than $f(g(x))$. This will be true for the case where $f$ is an increasing power tower of $x$'s.
Proof: Note, $f(g(x))=g(x)g(g(x))$ and $g(f(x))=g(xg(x))$. Thus, for sufficiently large $x$, $$\ln{f(g(x))}=\ln{g(x)}+\ln{g(g(x))}\leq 2\ln{g(g(x))}\leq x\ln{g(g(x))}$$ $$=\ln{g(g(x))^x}\leq \ln{g(xg(x))}=\ln{g(f(x))}.$$ Since $\lim_{x\to \infty} \frac{x\ln{g(g(x))}}{2\ln{g(g(x))}}=\infty$, then $g(f(x))$ grows asymptotically faster than $f(g(x))$.

Below are some more preliminary cases.

  1. If $f(x)$ and $g(x)$ have polynomial growth, then the rates are comparable for $f(g(x))$ and $g(f(x))$. In particular, if both functions are linear, then they commute $f\circ g=g\circ f$. Also, if $f(x)=x^m$ and $g(x)=x^n$, they commute. In general, if $f$ and $g$ are polynomials, whether $f(g(x))$ grows faster or $g(f(x))$ grows faster, depends on the leading coefficient. If $f(x)=ax^m$ and $g(x)=bx^n$ for $m,n>1$, then $f(g(x))$ grows faster, if $b > a^{\frac{n-1}{m-1}}$. If $b < a^{\frac{n-1}{m-1}}$, $g(f(x))$ grows faster. For example, if $f(x)=2x^3$ and $g(x)=x^2$, then $f(g(x))=2x^6<g(f(x))=4x^6$ for $x\geq 1$, despite that $\lim_{x\to \infty} \frac{f(x)}{g(x)}\to \infty$.
  2. If $f(x)$ has an exponential rate and $g(x)$ has a polynomial rate, then $f(g(x))$ grows faster than $g(f(x))$. Suppose $f(x)=\lambda^x$ for $\lambda>1$ and $g(x)=bx^n$. Then $f(g(x))=\lambda^{bx^n}>b\lambda^{nx}=g(f(x))$ for sufficiently large $x$.
  3. The situation flips when both functions have an exponential rate. In this case $g(f(x))$ grows faster than $f(g(x))$. Suppose $f(x)=\lambda^x$ and $g(x)=\beta^x$ where $\lambda>\beta>1$. Then $f(g(x))=\lambda^{\beta^x}$ and $g(f(x))=\beta^{\lambda^x}$. Take the logarithm of both sides, and we get for sufficiently large $x$, $$\ln{(f(g(x)))}=\beta^x \ln{\lambda}<\lambda^x \ln{\beta}=\ln{(g(f(x)))}.$$ Also, $\lim_{x\to \infty}\frac{f(g(x))}{g(f(x))}=0$.
  4. (added this case after comment) Suppose $f(x)=x^{x^x}$ and $g(x)=e^x$. Then $$f(g(x))={(e^x)}^{{(e^x)}^{(e^x)}}.$$ The function $g(f(x))=e^{x^{x^x}}$. Take the natural logarithm of both sides. $$\ln{f(g(x))}={(e^x)}^{(e^x)}\ln{(e^x)}=x {(e^x)}^{(e^x)}.$$ $$\ln{g(f(x))}=\ln{e^{x^{x^x}}}=x^{x^x}\ln{e}=x^{x^x}.$$ Note, $\ln{g(f(x))}=x^{x^x}$ grows faster, since there is a tower of 3 $x$'s. If we take the logarithm again, then it becomes clearer that $\ln{\ln{g(f(x))}}$ grows faster than $\ln{\ln{f(g(x))}}$. $$\ln{\ln{g(f(x))}}=x^x\ln{x}=x^{x-1}x\ln{x}>>\ln{x}+e(e^{x-1})x=\ln{x}+xe^x=\ln{(x(e^x)^{e^x})}=\ln{\ln{f(g(x))}}.$$
$\endgroup$
12
  • $\begingroup$ Intuitively I feel like this isn’t right… Say $f(x)$ denotes a power tower of $x$ $x$’s (say we are considering natural numbers), and $g(x)=e^x$, then it is clear $f$ is far faster growing, but when comparing compositions, it seems that $f(g(x))$ is the faster one $\endgroup$ Commented Aug 24 at 6:28
  • $\begingroup$ In my comment, the height of the power tower depends on the input (I realize this is sort of ambiguous since $e^x$ is not necessarily an integer, so say it is a tower of $\lceil x \rceil$ $x$'s). Then, we can see that for large $x$, $f(g(x))$ is a tower of $\approx e^x$ $e^x$'s whereas $g(f(x))$ is only $e$ raised to a tower of height $x$. So $f(g(x))$ seems to grow faster despite both functions growing at least as fast as $e^x$. $\endgroup$ Commented Aug 27 at 3:31
  • $\begingroup$ In $f(g(x))$, the power tower has height $\lceil g(x)\rceil$, i.e. height $e^x$, not $\lceil x \rceil$. $\endgroup$ Commented Aug 27 at 4:36
  • $\begingroup$ Essentially, I am defining the tetration function for $f(x)$ consisting of repeated exponentiation. I believe you can keep using higher order operations (pentation, hexation, ...) to keep giving counterexamples for all functions with growth at least tetration, pentation, etc. But this is not a proof that there is no "definitive rule" in terms of relative growth speeds, as there are functions that can grow faster asymptotically than this entire hierarchy $\endgroup$ Commented Aug 27 at 4:43
  • 1
    $\begingroup$ Thank you for providing context to your question. Agreed, you can take an arbitrarily fast growing $h(x)$, and for any strictly increasing $g(x)$ with $g(x)>x$, construct $f(x)$ such that $f(g(x))\geq h(g(f(x)))$. I've been interested in questions pertaining to scale and growth for many years. This is an interesting read: Scale: The Universal Laws of Growth, Innovation, Sustainability, and the Pace of Life in Organisms, Cities, Economies, and Companies. $\endgroup$ Commented Aug 29 at 12:42

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.