What is the O() runtime complexity of AdaBoost?

Question

I am using AdaBoost from scikit-learn using the typical DecisionTree weak learners. I would like to understand the runtime complexity in terms of data size N and number of weak learners T. I have searched for this info including in some of the original Adaboost paper from Yoav Freund and Robert Schapire and have not seen a very clear cut answer.

Answer 1

No disrespect meant to orgrisel, but his answer is lacking, as it completely ignores the number of features.

AdaBoost's time complexity is trivially O(T f), where f is the runtime of the weak learner in use.

For a normal style decision tree such as C4.5 the time complexity is O(N D^2), where D is the number of features. A single level decision tree would be O(N D)

You should never use experimentation to determine the runtime complexity of an algorithm as has been suggested. First, you will be unable to easily distinguish between similar complexities such as O(N log(N)) and O(N log(N)^2). It also risks being fooled by underlying implementation details. For example, many sorts can exhibit O(N) behavior when the data is mostly sorted or contains a few unique attributes. If you gave in an input with few unique values the runtime would exhibit faster results then the expected general case.

Answer 2

It's O(N . T). The linear dependency on T is certain as the user can select the number of trees and they are trained sequentially.

I think the complexity of fitting trees in sklearn is O(N) where N is the number of samples in the training set. The number of features also has a linear impact, when max_features is left to its default value.

To make sure you can write a script that measures the training time of adaboost models for 10%, 20%, ... 100% of your data and for n_estimators=10, 20, ... 100, then plot the results with matplotlib.

Edit: as AdaBoost is generally applied to shallow trees (with max_depth between 1 and 7 in general), it might be the case that the dependency of the complexity is actually not linear N. I think I measured a linear dependency on fully developed trees in the past (e.g. as in random forests). Shallow trees might have a complexity closer to O(N . log(N)) but I am not sure.