Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
add comment

6 Answers

up vote 11 down vote accepted

with small n big O 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 of 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 (theres also the stability issue)

also consider 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 consider: 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

share|improve this answer
    
Example of that last point - where it doesn't make much difference and naive may be the better choice - matrix multiplication - the naive approach is O(n^3), while the fastest ones are O(n^2.3727) but it doesn't make much of a difference unless you are dealing with matrixes that are huge... and the math is a lot harder to follow. –  MichaelT Apr 11 '13 at 0:45
1  
I'd also like to throw in this blog post on the topic, which I found to be a good rule of thumb. The thing to take away from it is that with O(n^3) and friends, "huge" could be as small as a few hundred items. Another good example is O(N!) - you will not be working out all combinations / permutations of more than one or two dozen items. Actually, I consider the usefulness of big-O to be the greatest exception to "what have you tried, and did you profile it?". I don't need to profile it to know that 100! is never going to happen. –  Daniel B Apr 11 '13 at 6:13
1  
It is important to realize that constants can be quite important. O(n) where single iteration takes a second may be worse than O(n log n) where you get a million iterations per second. –  SF. Apr 11 '13 at 15:02
add comment

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.

share|improve this answer
    
It's also worth thinking of the future. That dir algorithm that worked well in 1995 with 10s of subdirs on a local disk doesn't work so well with 100,000files on a NAS –  Martin Beckett Apr 11 '13 at 4:54
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.