Re:Ask HN: When was the last time you used big-o in a web app?
by Me1000 on Tuesday August 02, 2011 @09:05PM
(#2839374)
Quick follow up to clear up a couple questions that came up:
We only lay out visible rows, thus that layout is done in linear time, but calculating the position of those rows use the time complexities I described above.
For variable row heights we cache a few values for every single row up front, that is also linear.
The time complexity I'm describing in my original post is talking about calculating the position of those views are you scroll, draw, and layout (not the initial setup) ... which is what is most expensive.
A standard tableview (static row heights) is laid out in constant time, whereas using variable row heights is laid out in logarithmic time.
An early implementation provided variable row heights in linear time (or perhaps n^2, I don't recall)... this caused scrolling to be absolutely terrible and unusable if you had more than a couple dozen rows.
With constant time we can, theoretically, have any number of rows in your tableview and it will remain just as performant as if you only had 1.
If you're building real software and throw out the concept of time complexity, then you're setting yourself up for failure in the long run.