When would it be worth it to use a worse Big-O algorithm

Question

If there is a choice of algorithms of different time complexities, when would it be more worthwhile to choose a "worse" Big-O, such as picking O(n) instead of O(log n).

Answer 1

Big O means limit, infinitely many operations when our code works with finite number of operations (thus Big O is an approximation). Compare two time complexities:

t ~ 1e100 * N
t ~ N * N

Second algorithm (having a worse - N squared time complexity) is preferrable and faster for the real World input.

Answer 2

Complexity doesn't tell you anything about performance so it's not enough to know complexity to decide if an approach is worth over another. To know if one approach is better than another in a given situation (i.e. for a given problem size), benchmarking is the way to go. Once you benchmarked the different approaches, complexity can help you forecasting how things will scale when the problem grows in size.

Knowing the complexity of your algorithms can be quite useful - for example - in image processing:

imagine you have two different filters giving very similar results on a 2D image, one being faster than the other for "normal" images (some megapixels for example). How will they behave if you apply them to 3D images (i.e. what if the problem size is gigapixels instead)? Knowing the complexity AND having a reference benchmark can help you forecast what filter will be "worth" using, but in the end... you'll still benchmark both solutions to make sure.

Answer 3

Any asymptotic notation, describes how a certain algorithm behaves after a certain size of the input (n > n_0) is reached. What is typically not described is any additional constant multiplicative term that might be present (as well as other negligible terms, e.g. n^2 + n is of class O(n^2)).

For example, two algorithms with computational complexity 2 * n and 3 * n would be on the same O(n) class, while a 2 * n^2 algorithm would be in the O(n^2). Now, for small enough inputs (n = 1 in this example), the 2 * n^2 would execute more efficiently than the 3 * n algorithm.

This could be true also for O(n) versus O(log(n)) (or any other) computational complexities.