A biblioteca Scikit-Learn emprega o algoritmo Classification And Regression Tree (CART) para treinar Árvores de Decisão. O algoritmo CART baseia-se na recursividade e na estratégia de divisão binária para construir uma árvore de decisão. Inicialmente, a árvore é representada por um único nó, que contém todos os dados de treinamento. A cada passo, o algoritmo busca a melhor maneira de dividir o conjunto de dados. A recursividade continua até que uma condição de parada seja atendida, como atingir uma profundidade máxima da árvore. Uma vez construída a árvore, a fase de predição ocorre ao percorrer a estrutura da árvore de acordo com as condições estabelecidas nos nós, levando a uma predição (inferência) para uma determinada entrada.
Considerando-se que n corresponde ao número de features e m ao número de instâncias, qual é a complexidade computacional assintótica de predição para árvores de decisão treinadas com o algoritmo CART?