We have four categories:

additive constants, multiplicative constants, polynomials, and exponentials

When determining the growth order of functions, we only care about polynomials and exponentials and ignore additive/multiplicative constants.

To determine whether some arbitrary function f(x) is Big-O of another function, say, g(x), we can compute the limit of f(x) / g(x) as x tends to infinity.

However, it might be difficult to to evaluate this limit, and so we can evaluate the limit of log(f(x) / g(x)) instead.

I learned that when we evaluate the logarithm, we have to care about multiplicative constants as well. For instance:

f(x) = x^2

g(x) = x^3

log(f(x)) = 3 log x

log(g(x)) = 2 log x

In the example above, when using the logarithms to compare the growth order of f(x) to g(x), we have to consider the multiplicative constants in front of the log. This makes sense to me. However, my instructor also stated that conversely, when we exponentiate the term, then we "only care about exponentials." I'm paraphrasing what my instructor said, and I'm awfully confused by what he meant. When we take the logarithm, we consider multiplicative constants, but when we do the opposite--exponentiate--which of the four categories do we care about now?

  • $\begingroup$ I don't think this is a useful way of looking at things. Just stick to the definitions. In time, you will get intuition about asymptotic analysis, and such questions will disappear. $\endgroup$ – Yuval Filmus Sep 10 '19 at 8:28
  • $\begingroup$ I'm not sure what you mean by "four categories". Four categories of what? $\endgroup$ – Yuval Filmus Sep 10 '19 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.