Logarithm and the Expression of an Algorithm

I got to know about Logarithm in my High School.  But, I never knew it would be part of an engineer's life.  As a Software Test Engineer, I encounter the discussion that involves Logarithm often when testing an algorithm that is designed and implemented to solve a problem.

What is Logarithm?

I found this definition in Math is Fun. And, I see this is simple and straight.

How many of one number multiply together to make another number?

For example, how many of 4s make 64? 4 x 4 x 4 = 64.  

That is, when multiplied 3 of the 4s, I get 64.  Therefore, the logarithm is 3.

It is represented as below and said as "the logarithm of 64 with base 4 is 3".

• log₄₍64) = 3

The same can be written or expressed as exponent in Math.  That is, 4³ = 64.  The exponent and Logarithms are related.  The logarithm tells us what is the exponent.  

The logarithm answers the question -- What exponent do we need for the chosen base to get the given number?

John Napier introduced Logarithms in 1614 as means to simplify the calculations.

What Logarithm?

In the Computer Science, we use the Common Logarithm.  In my practice so far, when talking about the algorithms, I have been using Common Logarithm which is denoted using log.

The other type of Logarithm is, the Natural Logarithm. This is denoted using ln.

What is the Base?

One of the questions which is asked in discussion of an algorithm's analysis is what is the base?  This leads to question, What is the base that we should consider in Computer Science?

In my so far experience, I see, it depends on the context of an algorithm that is under evaluation and if it is of logarithmic nature in the time complexity and growth rate.

In the context of Computer Science, I see, the base do not matter much when equating the right hand side to the left hand side calculation.  But, one can pick the base that suits to context when needs to express the relationship of an algorithm under evaluation. The base need not be always 2 here.

Note: I understand below from the peer discussions for the logarithmic base in Computer Science:

The asymptotic notation focuses on growth rate and ignores the constant factors. Any two logarithms differ by a constant factor, and the base makes no difference.  Hence, I do not see base specified for a logarithm when using asymptotic notation.  That said, when I have a logarithm with a constant base, it is okay to not specify base.

When the base of logarithm depends on parameter (an input or any external configuration) to the algorithm and which is not constant, it is a better practice to mention the base.

In my testing experience for an algorithm's functionality, performance, complexity and growth rate, I see, the engineers keep the input parameters as configurable.  That is, it is kept as a constant which can be changed based on the need basis for the context.  So the base is not mentioned in the logarithmic expression for an algorithm most times.

If you see, my understanding is not appropriate in context of logarithmic asymptotic notation, do share your thoughts as comments to this blog post.  I will be happy to introspect and learn.

References:

• https://www.mathsisfun.com/algebra/logarithms.html