Time complexity analysis of random forest and k-means?

Question

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?

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.