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
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)$.
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?