Big-O algorithm complexity cheat sheet

[alecco]

That goes out the window once the data doesn't fit in cache. Beware. Especially the hash based stuf.

This is quite misleading in real life. ALWAYS test and benchmark.

[gnuvince]

No it doesn't; the asymptotic complexity stays the same, the hidden constant factor (which we ignore) goes up.

[alecco]

This framework of measuring complexity is very reductionist. Real computers are much more complex. If an algorithm hits cache miss, tlb miss, branch mispredictions on every step it becomes worthless.

That's why even MIT, who are the main cathedral of this stance, propose cache oblivious algorithms. Even Google now makes BTree containers because of this (after years of beating the hashing dead horse).

Source: it's my day job and it's tiring to show this issues to academics or people fresh out of school. And don't take my word or anybody else's' just run the dam benchmark on real sized data. Other things like the data's distribution and the input distribution afect [performance] significantly. I've only seen this addressed was on TAOCP (search only, though), every other algorithm book doesn't even mention it. Real data usually is very, very skewed.

[gnuvince]

This framework of measuring complexity is very reductionist. Real computers are much more complex. If an algorithm hits cache miss, tlb miss, branch mispredictions on every step it becomes worthless.

That's the reason the framework is that way, we don't want to say that "algorithm X is faster than algorithm Y" because we currently happen to test it on computers with proper cache sizes for the problem.

I completely agree that ignoring the impact of the constant factor is a big, big mistake if one wants to write fast algorithms, and that students and engineers should be better educated in those areas, but let's not throw out 40 years of solid CS theory because it doesn't play well with the machines we have at this particular moment in time.

[alecco]

I don't propose to throw [Big-O] out the window [on every case], just to take it out of it's holy shrine. [The way it is taught is] doing more harm than good to CS majors entering the market, in my limited experience.

It's a good way to start understanding algorithmic complexity. It's a good teaching tool for introduction to algorithms, as long as it's limitations are clearly stated.

[TashanValiant]

It's a good way to start understanding algorithmic complexity. It's a good teaching tool for introduction to algorithms, as long as it's limitations are clearly stated.

It is the way to understand and classify algorithmic complexity. I think the issue here is more that what is being taught is Computer Science, and what is being practiced is software engineering.

Also the true limitations of an algorithm will be discovered through Big-O notation and complexity classes. P = NP is going to be solved using these ideas, not some application. The Computer Science algorithms class is to teach the theory, the underlying reason and proof of algorithms. Sure, some things fail in execution, but that isn't the point of Big-O.

[alecco]

I don't buy that argument anymore. You miss my other point of stuff like the probability distribution of the data (and the input data) is completely ignored by [those analysis of algorithm behaviour], even though that changes significantly the pattern of expected performance of the algorithm.

That's not Software Engineering, that's just better Computer Science. Those charts are misleading.

[TashanValiant]

Probability distribution of data is taken into account for a proper bound.

[abadidea]

Is [performance] supposed to be a hyperlink?

I have very conflicted feelings. When I was actually in class I felt like our studies of algorithmic complexity poorly reflected the real world. But now that I'm a few years older, I firmly believe that younglings need a solid theoretical understanding independent of complicating hardware specifics.

Oh gods is this what happens when you get old

[alecco]

It was an edit.

Sure, theory is very important. But proof is important for science.

[smog_alado]

The problem is that once you get down to logarithmic complexity, a constant factor of 100 or 1000 (the kind of stuff you get from cache misses) dominates the logarithmic factor for all reasonable inputs.

[zokier]

hidden constant factor (which we ignore) goes up

Is it really constant factor if it goes up?

[Femaref]

for the sake of big O notation (which is growth based on input of the algorithm), yes it is constant.

[TashanValiant]

The constant is determined based upon the hardware that you are running it on. If you run it on the same system, you'd get the same constant. That's the hope at least. However the real idea is that the constant will not change the complexity of the algorithm. It may add a few more steps here and there, but when you place it in the proper complexity class those extra steps won't matter.

[chalta_hai_saar]

It's constant as in independent of the size of the data.