# Order of growth: substitution of monotonically increasing functions

One strategy for ordering the growth of functions involves substitutions when comparing functions using the limit as $n$ goes to infinity comparing two equations using the following rule.

$$\lim_{n\to\infty}\frac{f(n)}{g(n)} = \left\{ \begin{array}{cc} 0, & f(n) \in O(g(n)) \\\ \infty, & f(n) \in \Omega(g(n)) \\\ c\neq 0, & f(n) \in \Theta(g(n)) \end{array} \right.$$

Using a substitution was a new strategy to me, and it was explicitly used with logarithms because they are monotonically increasing. For example:

$$\lim_{n\to\infty}\frac{lg(n)^{lg(n)}}{2^{lg(n)}} = \lim_{k\to\infty}\frac{k^k}{2^k}$$

Obviously, this is a much easier problem to solve, and is much easier to prove in this form. The only two cases this was useful on the assignment I was working on was with logarithms, as in the case above, and iterated logarithms.

Are there other useful substitutions like this, or is there a broader implication of these monotonically increasing functions outside the realm of comparing order of growth? A big pet peeve is learning about a math concept in practice before in principle, because I don't feel like I understand the big picture. What realm of mathematics does this fall into?

• It's not important that logarithm is an increasing function. What we need is that if $k = \lg n$ then $n\to\infty$ iff $k\to\infty$. – Yuval Filmus Feb 20 '18 at 18:27
• Yes, good point. It only matters that $k$ is increasing because $n$ is increasing. But would its monotonic nature still be important? – zachsmthsn Feb 20 '18 at 19:53
• I don't think so. – Yuval Filmus Feb 20 '18 at 20:09
• No, monotonicity is nearly irrelevant. You can replace $\lg n$ by $\max_{k<n} {\lg k}$ and the behaviour at the limit is invariant. This you can do for almost any function – Discrete lizard Feb 20 '18 at 21:05