Perils of Time Complexity

Obviously, it is wise to avoid complexities such as O(n!) or O(2ⁿ). Likewise, it is usually an improvement to replace an O(n) algorithm with a functionally equivalent O(1) algorithm. This is not always the case, however, and a blind assumption should not be made based solely on big-o notation. Recall that, given O(g(x)), there is a constant, c, multiplied by g(x). Therefore, it is possible that an O(1) algorithm takes three hours to complete. Sure, it is always three hours, regardless of how large the input, but that can still be a long time compared to an O(n) algorithm with few inputs. The typical input size should always be taken into account when comparing algorithms.

Favor less complex algorithms, but keep in mind the overhead of the algorithm in relation to the typical input size. Do not optimize blindly for some random case!