4 ms·
Isn'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.
by jnurmine 8y ago
Isn'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.