As someone else pointed out, the render function is another interesting part where time can most likely be wasted. Unfortunately there's no way for us to know more.
In this case, it's not hard to reduce the constants to a point where the complexity doesn't really matter though.
The diffing operation is linear according to React documentation: https://facebook.github.io/react/docs/reconciliation.html
Is Array.prototype.concat linear, too? What about the ImmutableJS equivalent? I don't know a whole lot about algorithms, my intuition is that there would be a way to add an item to the end of the array without traversing the entire thing, but I guess it all depends on how the data structure is implemented.
Each time you add an item to a list of size n, it needs to process the previous n items. This forms the series 1+2+...+(n-1)+n, which is (n^2+n)/2.
Obviously a reference comparison is a lot quicker than a render, so you get big speed wins using immutablejs that are definitely worth it, but it's still O(n^2) components processed.