I agree that there are (rare) cases where the O notation isn't very helpful - e.g. the simplex algorithm actually being efficient despite its O(n3
) time complexity, or the linear-time polygon triangulation with a ~10150
constant (by Chazelle, the Clarkson/Seidel O(n log n) algorithm is faster for any polygon that fits into your RAM, that's for sure).
But in this case there are no hidden constants, and the O notation gives better results than your 2GHz-assumptions. (Or do you know what exactly is performed (data-)parallel, what kinds of pipelining optimizations can (not) be performed, if the amount of operations includes comparisons or only arithmetic operations, what the impact of the cache size and data locality is, how fast your FPU is and what can be performed parallel on it while the CPU does something else, ...? The factor you will be off is most likely > 100. The factor you will be off with the Big-Oh-calculus is in the same order, but it is (a) comparable (b) independent of hardware assumptions and (c) you see that the number of days is not important, while you were needlessly arguing with this value above. Plus, if it isn't "good enough", you can always count calculations, conditional statements etc. seperately. Or you could approximate constants. No matter what, you'll have something better than your wild guessing.
|Take HeapSort only, it has a worstcase complexity -O(n*log n).BUT, quicksort having worstcase O(n^2), is preferred over HeapSort due to the "SMALLER CONSTANT FACTOR" hidden in quicksort complexity|
What you describe has nothing to do with the "hidden constant", you compare different scenarios. Quicksort has an average case upper bound of O(n log n), and the O(n2
) case occurs with a probability of 1/n! (independent of the input, since the median determination it is based on the Monte-Carlo-method). Therefore it has about no impact on the average case, which is log(n!) = O(n log(n)) and occurring with a probability of ~1-1/n!. If you compare, please compare the same scenarios (and yes, QS is worse than HS in the worst case scenario. But not only in the Big-Oh-notation, also in reality).
In the analysis I gave, these cases are pretty much the same (worst case: all buildings have a different height, best case: all buildings have the same height, average case: the heights are uniformly distributed over the given range, which will result in ~b2
/(max height-min height) collisions - to few to mention in the given ranges, i.e. same as worst case).
If I read it right, your algorithm has one loop running b times, and an inner loop running "height" times, which might be a (quite large) value. It's obvious that this is painfully slow (as you will see if you perform some Big-Oh-calculations...).