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

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

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

<p><code>O(n.K.I.D) + O( j.log j)</code> where <code>j &lt;= n</code></p>

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

CC BY-SA 3.0
2013-09-26T07:49:02.803Z
2013-09-26T07:49:02.803Z
mamdouh alramadan
<p>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 </p>

<ul>
<li>$n$ is the number of points, </li>
<li>$K$ is the number of clusters, </li>
<li>$I$ is the number of iterations, </li>
<li>$d$ is the number of attributes. </li>
</ul>

<p>I am trying to calculate the time complexity for the algorithm</p>

<ol>
<li><p>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)$. </p></li>
<li><p>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. </p></li>
</ol>

<p>To get the complexity of the algorithm do i just add these two things?</p>

CC BY-SA 3.0
2013-09-14T14:02:49.103Z
Actually, $I$ could be exponential in $n$ if you run the algorithm to completion.
Jeffε
CC BY-SA 3.0
2013-11-25T10:24:11.837Z
What do you mean with "the random forest a divide and conquer approach"?
George
<ds.algorithms><time-complexity><clustering><decision-trees>
Time complexity analysis of random forest and k-means?
Eric Nunes
# Time complexity analysis of random forest and k-means?

(Asked by: username_0 on 2013-09-11)

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?

**Tags:** ds.algorithms, time-complexity, clustering, decision-trees
> **Comments:**
> **username_1**: Actually, $I$ could be exponential in $n$ if you run the algorithm to completion.  
> **username_2**: What do you mean with "the random forest a divide and conquer approach"?  

---

## 1 answers

### Answer by username_3 on 2013-09-26. Score: 0

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.


---

