# Time complexity analysis of random forest and k-means?

I am working with random forest for a supervised classification problem, and I am using the k-means clustering algorithm to split the data at each node, where

• $n$ is the number of points,
• $K$ is the number of clusters,
• $I$ is the number of iterations,
• $d$ is the number of attributes.

I am trying to calculate the time complexity for the algorithm

1. From what I understand the time complexity for $k$-means is $O( n \cdot K \cdot I \cdot d )$ , and as $k$, $I$ and $d$ are constants or have an upper bound, and $n$ is much larger than these three, i suppose the complexity is just $O(n)$.

2. The random forest on the other hand is a divide and conquer approach, so for $n$ instances the complexity is $O(n\cdot \log n)$, though I am not sure about this, correct me if i am wrong.

To get the complexity of the algorithm do i just add these two things?

• Actually, $I$ could be exponential in $n$ if you run the algorithm to completion. – Jeffε Sep 14 '13 at 14:02
• What do you mean with "the random forest a divide and conquer approach"? – George Nov 25 '13 at 10:24