Before we move to the time complexity of the next algorithm, I’ve decided to give it a break and write a short post about logarithms, they are crucial.
I’ll be honest, and I’ll confess that I always had a hard time understanding the concept of logarithms. While working with time complexities of the algorithms, we often come across “order of polynomials”. It could be 1, 2, half, so on, and so forth. But there is another one among these, and we consider it to be one of the best possible cases.
The logarithmic functions.
I read many times then I forget what it is. All I could remember was if the order of the function is logarithmic, it is a good thing. It started with the binary search tree algorithm where we divide the search criteria into halves as we move forward.
So, let me tell you how I understood what a logarithm is, and how it works. I hope it’ll help you too. At the end of this post, I have posted a link to the video which helped me to understand this concept.
A Logarithm is a way to express the exponential functions. We all know what exponential functions are, and we all know it hurts. In general, we write an exponential function as follows.
(Base) to the power (n) = result e.g. 1. 2^5 = 32 2. 10^2 = 100 3. e^x = n
In other words, we say that, if the base is multiplied by itself for ‘n’ times we get the result.
We can also refer to the base as the growth rate because that’s the factor by which we do the multiplication.
The power is the time, i.e. the number of times we are going to do the multiplication.
The result is the result.
Now for the same functionality, if we alter the equation and the definition, we will get the logarithmic function.
log (base) result = n (the power) e.g. 1. log (2) 32 = 5 2. log (10) 100 = 2 3. log (e) n = x // In all the above examples, consider the base to be written as a subscript.
That is to say, log Y of base X is the number of times (N) we need to multiply X with itself to get Y.
I hope this doesn’t sound confusing. Let us rephrase the definition of exponential functions using X, Y, and N.
Y is the result of X to the power N.
Explanation of logarithmic examples:
- To get 32 (the result) if the base is 2, we need to multiply 2; 5 (the power) times by 2 (the base, itself).
- To get 100 if the base is 10, we need to multiply 10; 2 times by 10.
- I hope this makes
I hope this makes the logarithms easier to understand if you had trouble understanding it.