Feb 24
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.
Conclusion
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!
Sign up for our Free Weekly Newsletter. Fresh content from developers all over the world, fresh and direct from the field! Don’t forget to follow our publication The Dev Project.
