How meaningful is the Big-O time complexity of an algorithm?

Question

Programmers often talk about the time complexity of an algorithm, e.g. O(log n) or O(n^2).

Time complexity classifications are made as the input size goes to infinity, but ironically infinite input size in computation is not used.

Put another way, the classification of an algorithm is based on a situation that algorithm will never be in: where n = infinity.

Also, consider that a polynomial time algorithm where the exponent is huge is just as useless as an exponential time algorithm with tiny base (e.g., 1.00000001^n) is useful.

Given this, how much can I rely on the Big-O time complexity to advise choice of an algorithm?

Answer 1

With small n Big O it is just about useless and it's the hidden constants or even actual implementation that will more likely be the deciding factor for which algorithm is better. This is why most sorting functions in standard libraries will switch to a faster insertion sort for those last 5 elements. The only way to figure out which one will be better is benchmarking with realistic data sets.

Big O is good for large data sets and discussing on how an algorithm will scale, it's better to have a O(n log n) algorithm than a O(n^2) when you expect the data to grow in the future, but if the O(n^2) works fine the way it is and the input sizes will likely remain constant, just make note that you can upgrade it but leave it as is, there are likely other things you need to worry about right now.

(Note all "large" and "smalls" in the previous paragraphs are meant to be taken relatively; small can be a few million and big can be a hundred it all depends on each specific case)

Often times there will be a trade-off between time and space: for example quicksort requires O(log n) extra memory while heapsort can use O(1) extra memory, however the hidden constants in heapsort makes it less attractive (there's also the stability issue which make mergesort more attractive if you don't mind payign the extra memory costs).

Another thing to consider is database indexes, these are additional tables that require log(n) time to update when a record is added, removed or modified, but lets lookups happen much faster (O(log n) instead of O(n)). deciding on whether to add one is a constant headache for most database admins: will I have enough lookups on the index compared to the amount of time I spend updating the index?

One last thing to keep in mind: the more efficient algorithms are nearly always more complicated than the naive straight-forward one (otherwise it would be the one you would have used from the start). This means a larger surface area for bugs and code that is harder to follow, both are non-trivial issues to deal with.

Answer 2

Very meaningful in my experience. At the root of many performance problems I often find these causes...

1. Failure to consider the range of n for which the algorithm will be used.
2. Failure to consider time complexity of the algorithm used.
3. Failure to consider memory requirements of the alogrithm for the likely range of n.
4. Failure to consider latency differences between RAM, Disk, Network, etc.
5. (and not least) Failure to test with realistic sized data.

This comes up in routine places in development of business software. Such as...

• Why does my SQL query run so slowly?
• Why does my HTML+CSS+js UI run so slowly? I'm just doing a few jquery operations on the DOM?
• Why is my .Net app running so slowly? I'm just using datasets to massage some data and put it in a grid.

In most cases where n is known to be small it's not worth spending a lot of time on complexity.

Thinking about the expected range of n and evaluating complexity is a proven way to know when it is worthwhile to question algorithms and architectures. I use this primarily as an intuitive tool for 'in my head' or 'back of cocktail napkin' level calculation. It saves me a lot of time.

It's an essential tool for software design.

Answer 3

What's important isn't the value that O bounds but the rate of growth of the value that O bounds. This is where Calculus comes in.

If you take the derivative of log(n) for instance, you get 1/n as the rate of change. This means that the time taken by a log(n) algorithm grows as a rate of 1/n meaning that as you add more and more values to the set, you get a smaller value for f(1/n). The same hold true over n'= 1, n^c' where c is some constant = cn and c^n' = c^n(log(c)). Thus you have a much, much slower rate of growth for time taken for the lower orders than for the higher ones. Once you hit exponential, the rate of growth begins to grow at a rate greater than the base function.

Thus understanding Big O allows you to easily compare algorithms time per input even if the input is never 'infinite'. Incidentally, infinite in software development or CS often means "Arbitrarily Large" rather than the technical, mathematical infinity since computers in practice are finite devices.

Answer 4

Asymptotic complexity is very meaningful indeed. Do you know the story about the inventor of chess, who asked the king to give him 2^65-1 grains of wheat as his reward? :)

You are correct, a polynomial algorithm of a high degree is likely to be useless. And to know that your algorithm's time complexity is a high degree polynomial, you have to look at the big-O. Also, a time complexity of O(1.00000001^n) is rare. But you see O(2^n) all the time, such as in the Boolean satisfiability problem.

If you do not understand the complexity of your algorithm, you can easily find yourself in a situation where your program works fine on a test input, but hangs when your customer gives it an input that is only twice as large.

Answer 5

I would say big-O analysis is not something you rely on, it's rather a kind of performance warnings.

If something is O(2^n), it doesn't mean it's slow, but it does mean that you should pay some attention to it.

If you optimise some algorithm, big-O analysis may show you which places should be measured first, because they are more likely to be bottleneck.

Answer 6

As others said, big-O matters if n can get large. The problem is, it's of such academic interest that it's taught heavily, so students end up predisposed to think it's the only thing that matters.

So if they get into projects where the constant factors are larger than necessary by orders of magnitude, they are so unprepared they often don't even recognize there might be a problem.

Constant factors are treated as an irrelevant afterthought, and students are told "use a profiler" (typically gprof), despite a poor track record of actually producing speedups.

Answer 7

Meaningful? Yes. But it doesn't tell the full story.

What the asymptotic complexity tells you is how well your program will scale with respect to the input size. For example, let's say you have a program that runs within an acceptable time for the time being on small inputs. Then the complexity will tell you a rough estimate of the time it takes to process something that's several factors larger.

What it doesn't tell you is how fast it will actually run, because you're still missing two critical bits of information:

• The coefficient / constant factor: if your algorithm is O(1) but the coefficient is enormous, then it probably won't be of much benefit unless you work with equally enormous inputs.
• The scaling for small inputs: asymptotic complexity describes the behavior as the input size approaches infinity. The behavior of the algorithm at small input sizes can be drastically different, however. Therefore, if your application involves primarily small inputs, then you should optimize for those instead of worrying about asymptotic complexity.

Asymptotic complexity is fine as a crude "zeroth-order estimate" for large inputs but what you really care is whether something performs acceptably on the inputs that matter to you. That will involve a more complicated mathematical calculation and/or profiling.

Answer 8

A specific thought on big-O from my practical experience: generally the linear factors dominate over constants for any decent size N. That is, an O(n^2) algorithm is generally awful compared to O(n), for data of any reasonable size. However, the logarithmic factors can be comparable to constants in many cases. In other words, even for N quite large, O(nlogn) may be comparable or even faster than O(n), depending on the constants. For instance, sometimes you can do the same problem where one of the steps is either by putting all the data in a hash table, which is O(n) time, or by sorting in O(nlogn). Sorting is usually very efficiently implemented in most languages, and hashing doesn't have the best constants necessarily, so I've seen sorting beat out hashing.