3
I have some questions about this complexity, which base is used in this logarithm, 2 or 10? and why? Searching Google I saw some comments saying that the base didn’t matter.. The logarithm is deeply connected to this complexity or is it used only to give an idea of how little complexity grows as n increases?
Last question, knowing only that while n grows exponentially, the search grows only linearly, would be enough to understand all other cases of complexity involving logarithm?
6
The basis doesn’t really matter much, because a logarithm of a base can be converted to another base by multiplying by a constant. For example: log2 10 = log10 10 / log10 2 (of which log10 2 is a constant), and the notation "Big O" exists precisely so that we can despise constants.
When it comes to computers, you can think in terms of the base 2 logarithm, because it matches well with "divide and conquer" algorithms, like looking for a binary tree, where doubling the number of elements increases the tree by only 1 level.
It hardly matters the absolute work that an algorithm does for a certain value of "n". What matters is the ratio between different values of "n", for example n=10 and n=1000000. If you log(1000000)/log(10), the result is always 6, no matter the basis of the logarithm, then whatever the basis, O(log n) correctly expresses the idea that n=1000000 costs only six times more work than n=10 for an algorithm O(log n).
Browser other questions tagged algorithm mathematics
You are not signed in. Login or sign up in order to post.
Possible duplicate of Definition of the notation "Big O"
– Sveen