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?

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

1 Answer 1


as it has been mentioned in the comment section, 'I' can be exponential in n if you run the algorithm to completion. which means you can't just cut down O(n.K.I.D) to be O(n). number of iterations can be just a big factor in your complexity.

for the second part I would also say no, you can't add the complexity like this.

let's say that your k-means is refining your data. Then, your n would become a j where: n >= j when you reach your random forest. so what you can say that the complexity here is:

O(n.K.I.D) + O( j.log j) where j <= n

I really don't have a valid proof here. but when you look at it. it just makes sense.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.