In what areas of programming is algorithm run time actually an important issue?

Question

Sometimes I hear people say that because of the speed of processors and the amount of memory available, algorithm efficiency and runtime aren't, in practice, of major concern.

But I imagine there are still areas where such considerations do remain of paramount importance. Two that come to mind are in algorithmic trading, where thousands of transactions must be conducted in fractions of a second, and embedded systems programming, where memory and power are often scarce. Am I right about these examples ? and what other areas would also be examples?

Answer 1

Speed is always in demand. I guess you are correct. Here are some examples were neat algorithms are in demand:

1. Cryptography

2. Searching large databases

3. Sorting and merging

4. Text searching (non-indexed), including wildcards

5. Math problems with intensive calculations

6. Simulation

7. Data Mining Applications

8. Animation

9. AI

10. Computer vision

Answer 2

There are some cases where algorithm run-time might not be a big deal, because we've gotten to the point that you can simply punch through a longer-running algorithm with more powerful hardware. But there are definitely some places where speed-ups are essential.

Generally speaking, anything using huge datasets will be a problem. When you have something that scales poorly with n, and then you make n a really huge number, you have a problem. I suspect if you went over to the Computational Science beta site and poked around a bit, you could find plenty of problems in need of better, faster algorithms. Some areas that I've run into:

• Particularly complex statistical analysis. A combination of inefficient algorithms and large data sets can mean massive slowdowns. For some studies, this might not matter, but what if you're trying to do something with fast turn around? "It will come off the server in a month" is probably a bad thing when you're running a chemical/nuclear/biological threat surveillance system.
• Data mining on large data sets.
• Simulations involving many variables.

Generally speaking, scientific computing generally seems to be an area where the complexity of what's being programmed generates opportunities for serious slowdowns if your algorithm is sluggish (many of them suffering from very large n's). And, as you mentioned, there's financial applications. When milliseconds can determine whether you make or lose money on a trade, "good enough" algorithms aren't going to cut it if there's something better that can be done.

Answer 3

Sometimes I hear people say that because of the speed of processors and the amount of memory available, algorithm efficiency and runtime aren't, in practice, of major concern.

Take it with a grain of salt. More computing power basically just means that your n can become much larger before it significantly slows down. For most everyday problems, this n is now large enough that you don't need to care. However, you should still know the complexities of your algorithms.

With more available resources, it may need to crunch more data later. Today you need to analyze a 10MB log file with 100,000 lines. In a year you may have a 100GB log file with 1,000,000,000 lines. If the amount of data grows faster than the resource powers, you run into problems later.

With more available resources, more layers are stacked upon each other. OS, OS framework, 3rd party framework, language interpreter, and finally on top your own tool. All unnecessary inefficiencies in all the different layers multiply up. Tomorrow your tool may run on a new OS with more bells and whistles, that itself eats more cycles and more memory, leaving less for you.

So to answer your question, you still need to care where more and more data needs to be crunched (enough examples given in the other answers), and where you do not provide the final tool, but another abstraction layer for other tools.

Answer 4

A few years ago I had to write an algorithm that sorted test tubes arranged on n racks into two distinct partitions: i.e. one subset of the tubes were 'chosen' and the rest were 'not-chosen' and the end result would be that no rack would have both a 'chosen' and 'not-chosen' tube on it (there were some extra requirements such as compression). Each rack contained a maximum of 100 tubes.

The algorithm was to be used to drive a tube sorting robot in a pharmaceutical laboratory.

When the original specification was given to me I was allocated in the region of 1 minute of calculation time to sort around 2000 tubes as we thought that usability wise that was not too painful. There was a requirement that number of moves was to be minimal over all possible combinations as the robot itself was slow.

The implicit assumption was that the complexity would be exponential with the number of tubes. However, whilst working on the algorithm design I discovered that there is a fast O(n) algorithm where n is the number of racks that performed an optimal partitioning of the tubes. The result of that was that the algorithm sort time was instant so the sorting display would be updated in real time as the user configured their sort operation.

For me the difference between the user sitting for a minute after every change and having an instantly responsive GUI was the difference between a piece of software that was functionally sufficient and a piece of software that was a pleasure to use.

Answer 5

Other areas include many kinds of real-time signal processing, feedback control systems, oil exploration deconvolution, video compression, ray tracing and movie frame rendering, virtual reality systems, games where high frame rate might be a significant competitive advantage, and smartphones and other mobile device apps, where large numbers of CPU cycles will consume the users battery life faster.

I'm quite surprised this question would even be asked, since for any Top-500 supercomputer ever built, there is likely a waiting list of researchers who can max it out and wish for magnitudes more compute power or magnitudes better algorithms to solve some problem (fold some protein to decipher cancer, etc.) before they retire.

Answer 6

Algorithm efficiency isn't a major concern nowadays because we're using efficient algorithms. If you used an O(n!) algorithm, it would be slow on any kind of hardware.

Answer 7

Algorithm complexity is becoming more and more important as the sheer amount of data increases. Fortunately, efficient generic solutions for common programming problems (searching and sorting, mainly) are included in pretty much every modern programming language's standard library, so normally, a programmer doesn't have to worry about these things much. The downside is that many programmers do not know at all what is going on under the hood and what the characteristics are of the algorithms they use.

This becomes especially problematic as many applications aren't properly stress-tested: People write code that works well for small test data sets, but when confronted with a few thousand times more data, the code grinds to a halt. Something that works well for ten records quickly explodes when the data set grows. Real-world example: a piece of code that was supposed to clean out items that weren't linked to any category anymore used a three-level nested loop, which is O(n^3). With just 10 records in the test database, this meant 1000 checks - perfectly doable, and doesn't introduce a noticable delay. However, the production database quickly filled with around 1000 rows, and suddenly the code does a billion checks each time.

So: No, you don't need to know the ins and outs of implementing all sorts of neat algorithms, and you don't need to be able to invent your own, but you do need some basic knowledge of common algorithms, what their strong and weak points are, when and when not to use them, and you need to be aware of the possible impact of algorithmic complexity, so that you can decide which level of complexity is acceptable.

Answer 8

I think search engines like Google and Bing are one of the biggest areas where complex algorithms are used and they play a key role in speeding up results with relevance ( page ranking ) bringing more utility to the users.

Answer 9

It's not a question of what application domains are runtime-sensitive. Any program, anywhere, has a minimum performance below which it is effectively worthless. The point of algorithm complexity is how it varies with increasing input size. In other words, the areas where speed particularly matters are those where you expect to have to scale beyond not just your current problem size, but the order of magnitude of your current problem size. If you process the tax applications of the citizens of a département of France, the task may be large, but it's not likely that either the population size or the complexity of processing one record will ever increase ten or hundred-fold, so whatever works for you now, will probably keep working. But if you try to create something that will take off at internet volumes, algorithm complexity is key: anything that depends more than linearly or log-linearly on the input size will become much more expensive very fast, and eventually processor speed just can't keep up with the growth.

Answer 10

Three more that haven't been mentioned:

1) Many real time strategy games. Look at those which have units which can't share a position. Watch what happens to the pathfinding when a large group of units moves through restricted terrain. I have yet to encounter a game without some sort of substantial problem with this because there simply isn't enough CPU power available.

2) Many optimization problems.

3) Things which must operate on large amounts of data in realtime. Consider a DVD: You usually get 2 hours of video in 4.7gb. Consider a typical video file at the same resolution: Those 2 hours of video will generally come in under 1gb. The reason for this is when the DVD spec was laid down you couldn't make a reasonably-priced DVD player that could decode the more modern formats fast enough.