Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right.
CART (Classification and Regression Trees) uses the Gini index for splitting (whereas Shannon's Entropy function is used in ID3). From what I know, it's asymptotic complexity can be represented as $O(n \log n)$, where $n$ is the number of samples and $m$ is the number of attributes.
Assuming $M$ to be the number of trees in a Random Forest, it's asymptotic complexity ought to be $M$ times that of CART, hence $O(Mnm \log n)$. This is neglecting the constant factors that scale linearly such as random selection of features for each tree of the forest.
Is this notion correct? Or is there more to this?