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 2, while the base 10 logarithm of 8 is0.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?

a, It's true that "f is order of log(n)" means different things for different bases of the log. When the base is not specified, it just means thatthe base is 10 by default.

b. It's true that "f is order of log(n)" means different things for different bases of the log. When the base is not specified, it just means thatthe base is e by default.

c. Actually, "f is order of log(n)" means the exact same thing regardless of the base.

More precisely, if a and b are two positive real numbers, then

f is of order if and only if f is of order .

The reason for that lies in the change of base formula, which says that any two log functions are in a constant positive factor relationship with each other. Order relations between two function do not change when you change a constant positive factor in one of the functions.

d. It's true that "f is order of log(n)" means different things for different bases of the log. When the base is not specified, it just means thatthe base is 2 by default. This convention is used because the worst case number of operations in binary search algorithms is a base-2 logarithm.