Question

You may have noticed that in practice problems related to order, logarithms are usually just "log". As you know from algebra, there is more than one logarithm. For each positive number b, there is a base-b logarithm. They are all different- the base-2 logarithm of 8 is 3, while the base 10 logarithm of 8 is 0.90308998699... . There is also a base-e logarithm, called the natural logarithm and usually written as "ln". This begs the question of how it could be justified to just say that a function f(n) is order of "log(n)". Isn't this meaningless if the base of the log is not specified?

Answer 1

Explanation:

A logarithm in one base is a constant multiple of a logarithm in any other base. Any "order of ..." specification does not include the applicable constant multiplier or the smaller order terms that may be required for an exact computation.

The concept of "order of" is similar to the concept of the degree of a polynomial. Knowing the degree of a polynomial tells you something about the "end behavior" as the function argument gets large. The specifics of the scale factor and lower-degree terms become largely irrelevant.