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
    
It depends on the complexity and the n. Below O(n^2) you can basically ignore it. Never write code above that without considering what the performance will be and profiling it for real-world n. (My personal highest was O(n^8), albeit somewhat sparse. 12 hour runtime on the real dataset. Going into it I knew that the task might prove infeasible.) –  Loren Pechtel Aug 17 at 15:53
    
Why do you say n = infinity? It doesn't have a maximum value, but it will always have a concrete value in your application. Or you plan on having up to n records in the future. –  Despertar Aug 17 at 17:07
    
There was a story about a scholar who performed a great service to a king in ancient times. The king offered a reward, so the scholar asked for a chessboard with 1 coin on the first square, 2 coins on the second and so on. The king readily agreed to such a simple (and obviously cheap) solution. Now, given this is a O(n^2) problem, do you think the king would have been happier if he'd known about big-O complexities? –  gbjbaanb Aug 19 at 7:40

8 Answers 8

up vote 20 down vote accepted

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).

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
1  
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
3  
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
2  
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
    
Well, neither quicksort nor heapsort come with stability guarantees, so that (specific) issue shouldn't be a deciding factor between them. –  Vatine Jul 9 at 0:29
    
Good point about efficient algorithms sometimes being more difficult to follow due to the complexity of the optimized code. This is a good argument for having very thorough test coverage on the classes and functions that implement those algorithms. –  Snowman Aug 18 at 21:24

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
1  
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
    
+1 for even just #1. All too often a quick test case goes "one, three...done, it works!" Then when it sees a realistic use scenario - kaboom –  BrianDHall Aug 18 at 20:26

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
    
+1 for mentioning the rate of growth. If I have a O(1) constant time algorithm, it doesn't necessarily mean its fast. It could take an hour to run. What it implies is that adding more records does not increase the time it takes to run. –  Despertar Aug 17 at 17:13

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

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

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
    
Throughout the course of a B.S. and M.S. in computer science, I do not believe I ever had a professor even say the word "profiler." I am much more likely to receive that advice on this site. –  Snowman Aug 18 at 21:37
    
@Snowman: Right, and when they do mention "profiler", they mention "gprof" in the same breath, which in my opinion is worse than saying nothing. Check the second answer here. –  Mike Dunlavey Aug 19 at 1:04
    
On one hand I feel ashamed not to have heard of gprof before. On the other hand, I feel grateful. And I have almost 15 years of experience in this career field. –  Snowman Aug 19 at 4:29

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.

share|improve this answer

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.

share|improve this answer
    
this doesn't seem to offer anything substantial over points made and explained in 6 prior answers –  gnat Aug 17 at 18:06
    
Except that the entire post is a very specific comment on the contrast between proportional and logarithmic factors, the two most common kinds, followed by an even more concrete example of how many problems can be solved in two ways, and the times are comparable despite differing big O? Like, are you bored and just looking for something to -1? It adds a particular piece of information and doesn't overlap the previous answers, there's no justification to -1 it. –  Nir Friedman Aug 18 at 1:15
2  
Mike Dunlavey's answer talks about the constant factors as well. –  Snowman Aug 18 at 21:41

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.