What does logarithmic mean in algorithm cost?

Question

Sklearn says about decision trees:

The cost of using the tree (i.e., predicting data) is logarithmic 
in the number of data points used to train the tree.

I know a logarithm as the inverse to an exponential function. What does it mean in this context? I have the feeling that it references an exponential function such as 2**n possible nodes or such.

However, my understanding it quite vague and I want to get a better picture.

It's saying if there's N data points, then the cost of whatever it's talking about is O(log N). — Paul Hankin, Sep 30 '17 at 11:14
It usually implies that there is a *divide-and-conquer* element to the algorithm, if that's what you mean — meowgoesthedog, Sep 30 '17 at 14:46

score 2 · Accepted Answer · answered Sep 30 '17 at 11:15

2

See What is a plain English explanation of "Big O" notation? or many other similar explanations first for what O(f(N)) means. In this case you have O(log N): when the number of data points doubles, the cost increases by a constant.

answered Sep 30 '17 at 11:15

Alexey Romanov

167,066
35
309
487

score 0 · Answer 2 · answered Sep 30 '17 at 11:15

0

Very briefly:

O(1) < O(log N) < O(N)

Logarithmic is cheaper than a linear (i.e. O(N)) cost.

Wikipedia has a nice table that orders the different big-O costs.

answered Sep 30 '17 at 11:15

Phylyp

1,659
13
16

1

using `<` in this context may be misleading. It may well be that for a certain N the O(1) algorithm is much worse than the O(N) one. The inequality becomes only true for large enough N. In fact, many theoretically good algorithms are practically irrelevant because the necessary problem sizes never occur in practice. – Henry Sep 30 '17 at 11:21

What does logarithmic mean in algorithm cost?

2 Answers2