What is the runtime complexity of training a forest of T extremely randomized trees in terms of the Big O notation?

If n is the number of samples and there are m attributes then tree learning is O(m* n* log n), a Random forest which optimises for best split is O(T* m* n* log n) where there are T trees.

For extremely randomised trees where we don't optimise for best split locally we drop the linear dependence on n, so it is O(T* m* log n)?