Hacker News Reader

Comment by jedberg | Hacker News Reader

Honestly, I've never heard a term for it. Just talked about in the abstract:

"That operation is O(n log n)"

"Sure, but that operation doesn't happen on every loop, the entire algorithm is still O(n)".

I'm old enough to remember that Microsoft got this wrong back in the early 90s. In early versions of Microsoft Foundation Classes, which Windows C++ programmers were using before the STL took over and std::string became the thing, repeatedly appending a character to a string (I think it was CString) was quadratic, because they didn't increase array size by a multiplicative factor, but by a linear amount, so you'd get a ton of reallocation and copying. I used to use versions of this as an interview question.

However, language for concepts evolves with time, and younger programmers shouldn't assume that older programmers don't know a concept because they learned it by a different name. (Though they might not know the concept).

In early versions of Microsoft Foundation Classes … repeatedly appending a character to a string (I think it was CString) was quadratic, because they didn't increase array size by a multiplicative factor, but by a linear amount, so you'd get a ton of reallocation and copying.

I remember seeing production code slow to a crawl once because of that one. It wasn’t long after I’d left university, where I’d studied CS but the lectures on complexity theory had seemed quite theoretical at the time. Suddenly, here was a vivid example of how it could cause a problem in practice, in a situation as everyday as putting some text in a UI. The solution — using a string builder — then led me to several other principles about choosing an efficient internal representation for data and it being OK not to convert that data into its “true” form until you’re ready to use it. I suppose I should thank whoever made the original mistake, because despite causing a frustrating afternoon with a profiler, it also created several lightbulb moments early in my career.

It reminds me a bit more of talking about p50 vs p99 latency times but where we’re not measuring production data, more like what we’re guessing production loads will look like.

Reply on news.ycombinator.com