2 ms·
I am always uncomfortable with high "big O" algorithms. For example I know that with the data we have now, O(n^2) is fine, but if there is no strict bound on n,
by GuB-42 7y ago
I am always uncomfortable with high "big O" algorithms. For example I know that with the data we have now, O(n^2) is fine, but if there is no strict bound on n, we don't know how far n will go in the future. It may also be a vulnerability, where the attacker uses data that is designed to exploit the worst case scenario.
It is more about peace of mind. By using the more efficient algorithm (by asymptotic complexity), I know that my code won't become a bottleneck. That's like using "size_t" instead of "int" in C. I know my array will not exceed 4GB in any practical application, but by using size_t, I know it won't crash if it happens one day. One less thing to worry about.
Almost all well designed libraries use hybrid approaches, switching from an algorithm optimized for low level efficiently for low N to a theoretically more efficient algorithm for high N. For example a sorting algorithm can go from insertion sort (good for low N) to quicksort (very efficient most cases) to merge sort (guaranteed nlog(n), highly parallelizable).