3 ms·
an O(N^2) algorithm could be useless, if it's a galactic algorithm: https://en.m.wikipedia.org/wiki/Galactic_algorithm https://en.m.wikipedia.org/wiki/Galactic_
by sterlind 3y ago
an O(N^2) algorithm could be useless, if it's a galactic algorithm: https://en.m.wikipedia.org/wiki/Galactic_algorithm https://en.m.wikipedia.org/wiki/Galactic_algorithm
conversely, theoretically an O(N^100) algorithm could be practical if it's ~N^2 in practice except on very rare instances. remember big-O is an upper bound.
- tsimionescu 3y agoSure, there are even more caveats. I should note though that big-O is not technically an upper bound on program execution time (worse case scenario), you can use big-O to refer to the best case scenario or the average case. Big-O is a notation for fhe upper bound of a function in general (e.g. f(x) = x^2 + 70x + 9 is in O(x^2)). I think it's reasonable in this kind of case to assume we are speaking about the average-case complexity, though it's true that many think of worse case, taking the upper bound of the upper bound of the number of execution steps.