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?
- log4(64) = 3
The same can be written or expressed as exponent in Math. That is, 43 = 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?
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.
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