I have some questions about this complexity, what base is used in this logarithm, 2 or 10? it’s because? Looking at google I saw some comments saying that the base did not matter .. Is the logarithm deeply linked to this complexity or is it used only to give an idea of how little complexity grows as
Last question, knowing only that while
n grows exponentially, the search grows only linearly, would it be enough to understand all other cases of complexity involving logarithm?
When it comes to computers, you might think in terms of base 2 logarithm, because it marries well with “divide and conquer” algorithms like search in a binary tree, where doubling the number of elements increases the tree by only 1 level.
It hardly matters what absolute work an algorithm exerts 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 equal to 6, no matter the basis of the logarithm, so 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).