[BFay]

Is the complexity actually quadratic, like amelius said?

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.

[ajanuary]

I've been pretty vague which probably isn't very helpful so I'll try to be a bit more precise: for a mutable implementation it's quadratic in the number of times render is called over the lifetime of the component; for an immutable implementation it's quadratic in the number of comparisons (inside shouldComponentUpdate) over the same lifetime. You can generalize both operations to "process component when building the component tree".

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.

[i_s]

A component being processed via returning false from shouldComponentUpdate is very very different from a component being processed by running the render method and then doing a diff, so that is not a good model.