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?

  • $\begingroup$ 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$. $\endgroup$ Commented Feb 20, 2018 at 18:27
  • $\begingroup$ Yes, good point. It only matters that $k$ is increasing because $n$ is increasing. But would its monotonic nature still be important? $\endgroup$
    – zachsmthsn
    Commented Feb 20, 2018 at 19:53
  • $\begingroup$ I don't think so. $\endgroup$ Commented Feb 20, 2018 at 20:09
  • $\begingroup$ 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 $\endgroup$
    – Discrete lizard
    Commented Feb 20, 2018 at 21:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.