[Clus-general] Training computational complexity of RF-PCT

[Nair b. N. Y. <nai...@ya...>]

Hello,
I have a question about the training computational complexity of the random forest of clustering trees (RF-PCT) algorithm. In the papers, the authors mention that it is around O(100 x n x m_i x log(n)) where 
1. m_i: number of features selected at each node, representing 10% of the original number of features2. n: number of training examples

However, it seems that they ignore here the number of labels. If we imagine  having to learn from a large dataset with hundreds or thousands labels, how would you rewrite this training computational complexity ?
is it O(100 x n x q x m_i x log(n)) where q is the number of labels ?

Thanks !
NAIR BENREKIA Noureddine YassinePhD student at Orange Labs, Lannion (France