Comment by mytherin

> Well, that is an abuse of the term, by people that sometimes don't actually know what that really means. Up to a point, quadratic IS faster than linear after all for example. Too many developer love too abuse the word blindly.

There is absolutely no guarantee that a quadratic algorithm has to be faster than a linear algorithm for small N. It can be, in some situations for some algorithms, but the complexity class of the algorithm has nothing to do with that. A quadratic algorithm may well be slower than a linear algorithm for any N.

The only thing the complexity class tells us is that starting from some N the linear algorithm is faster than the quadratic algorithm. That N could be 0, it could be 100, or it could be 1 billion.

In my experience it's usually between 0~1000, but again, that depends. The complexity class makes no such guarantees. The complexity class tells us the general shape of the performance graph, but not exactly where the graphs will intersect: this depends on the constants.

> If it is badly tested with no data, it is badly tested with no data. Period. Not "quadratic".

It is both. The problem is that the algorithm has quadratic complexity. The fact that it was badly tested caused this fact to remain hidden while writing the code, and turn into a real problem later on.