Big Notation O - Complexity O (log n)

Question

Big Notation O - Complexity O (log n)

Navigation

#1 by (6 votes)

3

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 n increases?

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?

algoritmo

asked by anonymous 01.04.2018 / 06:59

1 answer

How to access and stop a Thread? ASP.NET C # Desktop widgets in Java

score 6 · Accepted Answer

The basis really does not matter much, because a logarithm of a base can be converted to another base by multiplying it by a constant. For example, log 2 10 = log 10 10 / log 10 2 (where log 10 2 is a constant), and the notation "Big O" exists just so we can disregard constants.

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).