2 ms·
Yes I agree. What I think is misleading about the general use of O() by programmers is that it is an theoretical construct and other discountineous effects lik
by rightbyte 8y ago
Yes I agree.
What I think is misleading about the general use of O() by programmers is that it is an theoretical construct and other discountineous effects like cache misses (cache size) etc is not taken into consideration and further more the range of n:s for which each algorithm is fastest is often ignored.
Some dummy numbers:
T1 = 0.0000001 n^2 + n
T2 = 100000000 n
Would yield:
O1(n^2)
O2(n)
Long before n is big enough for a hypothetical server running the O(n^2) algorithm to be slower than the O(n) other effects might cap it.
The best way to find out is empirical testing.
- jnurmine 8y agoIsn't the point the order of growth...? If you double the input size, O(N) will run twice as long, whereas O(N^2) four times as long.
- rightbyte 8y agoNo, that's only true at the limit as n goes towards infinity. And even if you see it as a approximation of growth for big n:s, you need to know "twice what" and "four times what" and "what's a big n" to have any use from it. For the example with multiplication of 2 n-digit numbers: https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm It's O(n^1.585). Need about 1000 digits before it's actually faster than "School book" O(n^2) multiplication. https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse... It's O(n log n log log n). In practice faster than Karatsuba at 10,000 to 40,000 decimal digits. Then there is the newest and hottest O(n log n) version, that's not practical at all.
- brucedawson 8y agoSure, there are some cases where O() can be misleading, but those are the exceptions. You can work in software for a long time without being affected significantly by them, whereas using O(n^2) when you could use O(n) can make your code 1,000 times slower than usable, and it does this frequently. I have fixed hundreds of O(n^2) algorithms over the years, made them O(n) or O(n log(n)), and made the product dramatically better. The fact that an O(n) algorithm can sometimes be slower than an O(n^2) feels more like pedantry than useful information in this context.