CODEWITHSUNDEEP
algorithm
shredding
shredding

Reputation: 5591

What does logarithmic mean in algorithm cost?

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.

Upvotes: 0

Views: 340

Answers (2)

Phylyp
Phylyp

Reputation: 1689

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.

Upvotes: 0

Alexey Romanov
Alexey Romanov

Reputation: 170745

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.

Upvotes: 2

Related Questions