4 ms·
This mainly shows that the author mistakes the prupose of Big-O notations. It's a measure of asymptotic performance, so there need to be an asymptote to reach.
by pierrebai 9y ago
This mainly shows that the author mistakes the prupose of Big-O notations. It's a measure of asymptotic performance, so there need to be an asymptote to reach. If the range of values you're measuring is small (and a non-constant factor that varies between 1 and 6 is small) then it's teh fact that one uses Big-O to characterize an algorithm that is wrong.
It's a classic mistake. There are many pitfall to performace measurements, including: using Big-O when the range is small or ignoring cinstant factor when the constant is big. Both of these has lead people down the wrong path, for example usng a theoretically faster algorithm that is in reality slower because in the typical use case the constant overweigh the complexity factor.
The counter-example to the author argument would be to say that a binary decision is linear over the input range.
- flgr 9y ago> and a non-constant factor that varies between 1 and 6 is small Wouldn't the 6 in O(((n^1000)^n)^6) be a non-constant factor that makes a big difference in asymptotic performance though?
- mamon 9y agoThis is not a constant factor, this is an exponent. Constant factors are what's standing in front of whole term, like this: O(7*((n^1000)^n)^6), 7 being constant factor.
- kbenson 9y agoI think the problem is confusion as to whether it's being applied to the algorithm, or the implementation. The algorithm is not effectively constant time, as n is infinite. The implementation, which has an upper bound for n, is effectively constant because of that limitation.