Scribd
Upload
7 views1 page

Decision Tree and Random Forest Complexity

The document outlines the operations and time complexities of Decision Tree and Random Forest algorithms. It details the pseudo-code for various methods including tree construction, fitting, and prediction, along with their respective time complexities based on parameters like number of samples, depth, and features. Key functions such as finding the best split and calculating information gain are also included with their computational costs.

Uploaded by

Fati Lamrani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views1 page

Decision Tree and Random Forest Complexity

The document outlines the operations and time complexities of Decision Tree and Random Forest algorithms. It details the pseudo-code for various methods including tree construction, fitting, and prediction, along with their respective time complexities based on parameters like number of samples, depth, and features. Key functions such as finding the best split and calculating information gain are also included with their computational costs.

Uploaded by

Fati Lamrani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Operation/Method Pseudo-code Description Time Complexity

Decision Tree
Constructor Initialize max_depth and empty O(1)
tree
fit Build tree from training data O(n * d * f) where:
n = number of samples
d = max depth
f = number of features
predict (single) Navigate tree from root to leaf O(d) where :
d = depth of tree
predict (all) Predict for all samples O(n * d) where:
n = number of samples
construire_arbre Recursively build tree structure O(n * d * f) due to splitting
at each level
trouver_meilleur_split Find best feature and threshold O(n * f * v) where:
- n = number of samples
- f = number of features
- v = unique values per
feature
calculer_gain_information Calculate information gain for O(n) for counting and
split entropy calculation
calculer_entropie Calculate entropy of subset O(n) for counting class
frequencies
prédire_ligne Traverse tree for single O(d) where:
prediction - d = depth of tree
Random Forest
Constructor Initialize parameters O(1)
fit Build multiple trees with O(t * n * d * f) where:
bootstrapped samples - t = number of trees
- n = sample size
- d = max depth
- f = number of features
predict Get predictions from all trees O(t * n * d) where:
and vote - t = number of trees
- n = number of samples
- d = depth of trees
vote_majoritaire Count most frequent prediction O(t * n) where :
t = number of trees

You might also like