Consider two different classifiers learning over the same training set, which contains N examples, each with m Boolean features.

We know that logistic regression reaches 100% accuracy on the training data.

Is there a bound on the depth of a decision tree that is guaranteed to fit the training data perfectly?

I.e. can you say that "this can be done in a depth of at most ....." ?

• If yes, state the depth and give a 1-2 lines explanation.
• If there is no bound or if a decision tree is not guaranteed to yield 100% accuracy on the training data, then argue that briefly (1-2 lines).

I.e, in either case, state your answer and give a 1-2 line explanation in the allocated location below (i.e. this is not a handwritten question).