The Dev Project
Published in

The Dev Project

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.

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.

--

--

--

The Dev Project is a journey that will never stop, it’s fun and with a lot of challenges, in this publication space you will find many pieces of information about the Development World.

Recommended from Medium

Positive Organizational Impacts of Cloud Transformation

Docker NodeJS MongoDB

D&D Character Creator… too ambitious for my first website?

Awesome software makes you creative.

Four things I learnt from my first code sprint!

Just add RSpec!

All about OpenCV built-in functions

Optimizing Serverless in AWS

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Seen So

Seen So

Software Engineer // Normal Human

More from Medium

Interview with Erion Adams, Emerging Tech Developer

Erion Adams

Arrays, what are they essentially?

Recursion forever

What is Recursion ? What is Recursion ? What is Recursion ?