Logarithm Complexity vs Linear Complexity
I will explain why the logarithmic time complexity is better than the linear time complexity. Yes, the same logarithm that you learned in math class. The one that says
logb(x) = y, if and only if b^y = x.
In the software industry, the logarithm is used to describe the time complexity of an algorithm and a base of 2 is always implied (b in the above formula would equal 2 in this case). So that would mean that we are looking at the following formula:
log2(n) = y, if and only if 2^y = n. Where n replaces x since the Big O Notation states “log(n).” We also assume that the logarithm is the binary logarithm, so don’t need the base of 2 in “log2(n).” We can remove it and just say
log(n) = y, if and only if 2^y = n.
For an overview on Big O Notation, take a look at the article below.
When you increase the power of 2, you are doubling the number. In
2^y = n we can say that every time n doubles, we are increasing y by 1. When we have an algorithm with a O(log(n)) time complexity, it’s a very good thing. We know that in a logarithmic complexity, as input doubles, the number of operations performing in the algorithm only increases by 1. Whereas in a linear time complexity, when an input doubles, so does the number of operations in the algorithm.
That’s why logarithmic time complexity is better than linear time complexity!