3 ms·
When you do big O analysis you get best case, worst case, and average case. You have to do some thinking about the structure of you data when doing big O analys
by samfisher83 7y ago
When you do big O analysis you get best case, worst case, and average case. You have to do some thinking about the structure of you data when doing big O analysis.
- saagarjha 7y agoNo, the point here is that big-O analysis means nothing if n is small. If n < 10 your algorithm could be exponential and still do better than a linear algorithm with a constant factor a thousand times larger.
- TeMPOraL 7y agoIt's not that. Something not properly covered in CS courses is that very often, performance is dominated by things that are not evaluated as a part of big O analysis. Like, memory allocations, cache friendliness, and other constant factors. For example, according to the theory, a hash table is much better suited for key lookup and random additions than a vector. In practice, if you're storing a couple hundred elements, a flat array (with objects stored directly) will be faster because of data locality. If your problems are mostly "do a lot of small N ops" and not "do some large N ops", then big O analysis isn't all that useful anymore.
- seanmcdirmid 7y agoThis is covered in computer architecture, at least, and sometimes (but not often) in compilers.
- samfisher83 7y agoThat is taught in your compilers class.