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 — willywonkadailyblah, 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

160,869
33
291
457

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,594
11
15

1

using ` – Henry Sep 30 '17 at 11:21

What does logarithmic mean in algorithm cost?

2 Answers2