Are algorithms (and efficiency in general) getting less important?

Question

Since buying computation power is much affordable than in the past, are the knowledge of algorithms and being efficient getting less important? It's clear that you would want to avoid an infinite loop, so, not everything goes. But if you have better hardware, could you have somehow worse software?

Answer 1

I really like the example from Introduction to Algorithms book, which illustrates significance of algorithm efficiency:

Let's compare two sorting algorithms: insertion sort and merge sort. Their complexity is $O(n^2) = c_1n^2$ and $O(n\log n) = c_2n \lg n$ respectively. Typically merge sort has a bigger constant factor, so let's assume $c_1 < c_2$.

To answer your question, we evaluate execution time of a faster computer (A) running insertion sort algorithm against slower computer (B) running merge sort algorithm.

We assume:

• the size of input problem is 10 million numbers: $n=10^7$;
• computer A executes $10^{10}$ instructions per second (~ 10GHz);
• computer B executes only $10^7$ instructions per second (~ 10MHz);
• the constant factors are $c_1=2$ (what is slightly overestimated) and $c_2=50$ (in reality is smaller).

So with these assumptions it takes

$$ \frac{2 \cdot (10^7)^2 \text{ instructions}} {10^{10} \text{ instructions}/\text{second}} = 2 \cdot 10^4 \text{ seconds} $$ for the computer A to sort $10^7$ numbers and

$$ \frac{50 \cdot 10^7 \lg 10^7 \text{ instructions}} {10^{7} \text{ instructions}/\text{second}} \approx 1163 \text{ seconds}$$

for the computer B.

So the computer, which is 1000 times slower, can solve the problem 17 times faster. In reality the advantage of merge sort will be even more significant and increasing with the size of the problem. I hope this example helps to answer your question.

However, this is not all about algorithm complexity. Today it is almost impossible to get a significant speedup just by the use of the machine with higher CPU frequency. People need to design algorithms for multi-core systems that scale well. This is also a tricky task, because with the increase of cores, an overhead (for managing memory accesses, for instance) increases as well. So it's nearly impossible to get a linear speedup.

So to sum up, the design of efficient algorithms today is equally important as before, because neither frequency increase nor extra cores will give you the speedup compared to the one brought by the efficient algorithm.

Answer 2

On the contrary. At the same time that hardware is getting cheaper, several other developments take place.

First, the amount of data to be processed is growing exponentially. This has led to the study of quasilinear time algorithms, and the area of big data. Think for example about search engines - they have to handle large volumes of queries, process large amounts of data, and do it quickly. Algorithms are more important than ever.

Second, the area of machine learning is growing strong, and full of algorithms (albeit of a different kind than what you learn in your BA). The area is thriving, and every so often a truly new algorithm is invented, and improves performance significantly.

Third, distributed algorithms have become more important, since we are hitting a roadblock in increasing CPU processing speed. Nowadays computing power is being increased by parallelizing, and that involves dedicated algorithms.

Fourth, to counterbalance the increasing power of CPUs, modern programming paradigms employ virtual machine methods to combat security loopholes. That slows these programs down by an appreciable factor. Adding to the conundrum, your operating system is investing more CPU time on bells and whistles, leaving less CPU time for your actual programs, which could include CPU-intensive algorithms such as video compression and decompression. So while hardware is faster, it's not used as efficiently.

Summarizing, efficient algorithms are necessary to handle large amounts of data; new kinds of algorithms are popping up in the area of artificial intelligence; distributed algorithms are coming into focus; and CPU power is harnessed less efficiently for various reasons (but mainly, because computers are getting more powerful). Algorithms are not dead yet.

Answer 3

The knowledge of algorithms is much more than how to write fast algorithms.

It also gives you problem solving methods (e.g. divide and conquer, dynamic programming, greedy, reduction, linear programming, etc) that you can then apply when approaching a new and challenging problem. Having a suitable approach usually leads to codes which are simpler and much faster to write. So I have to disagree with Kevin's answer since codes that are not carefully put together are often not only slow but also complicated. I like this quote by David Parnas:

I often hear developers described as "someone who knows how to build a large system quickly." There is no trick in building large systems quickly; the quicker you build them, the larger they get!

(Of course, we also need to combine algorithms with software design methods to write good codes.)

The knowledge of algorithms also tells us how to organize your data so that you can process them more easily and efficiently through the use of data structures.

Furthermore, it gives us a way to estimate the efficiency of your approach, and to understand the trade-offs between several different approaches in term of time complexity, space complexity, and the complexity of the codes. Knowing these trade-offs is the key to make the right decision within your resource constraints.

On the importance of software efficiency, I will quote Wirth's Law:

Software is getting slower more rapidly than hardware becomes faster.

Larry Page recently restated that software gets twice as slow every 18 months, and thus outpaces Moore’s law.

Answer 4

Yes, they are 'relatively' less important in wide industry. Text editor may be 'fast enough' and it might not need much improvements. Large part of IT effort goes to making sure component A written in Java works with component B written with C communicates correctly via message queue written in Cobol (or something), or to get the product to the market etc.

Furthermore the architecture got complicated. When you had plain old simple processors where you had 1 instruction per cycle and you wrote in assembly the optimizations were 'easy' (you just needed to count number of instructions). Currently you don't have a simple processor but a fully-pipelined, superscalar, out-of-order processor with register renaming and multiple level cache. And you don't write in assembly but in C/Java/etc. where code's compiled/JITed (usually to better code then you or I would wrote in assembly), or in Python/Ruby/... where code is interpreted and you are separated by several level of abstraction from machine. Microoptimalizations are hard and most programmers would achieve opposite effect.

No, they are as ever as important in research and in 'absolute' terms. There are areas where speed is important as they operate on large amount of data. On this scale the complexities matter as shown by Pavel example.

However there are further cases - going 'down' from algorithms is still an option chosen when speed matters (HPC, embedded devices etc.). You will find on many universities groups specializing in compilers and/or software optimization. For example a simple swap of loop ordering can get a thousand time speedup just because it utilizes cache efficiently - while it might be a borderline example the CPU-Memory gap grow 1000 times over past 30 years. Also Computer Architecture is part of CS. Therefore many of the improvements in speed of computation are in fact a part of general CS field.

On the industrial side - when you have a HPC cluster speed matters because single program can run for days, months or years. Not only you need to pay the electricity bill but waiting also can cost money. You can throw twice as much hardware but 700M$ can be hardly considered a pocket change for all but biggest companies - in such cases the programmers are the cheaper option and if rewriting the program into new language mean just a 'small' speedup - they might consider it.

Also speed might mean better UX. Many reviews of mobile phones OS states which one is 'snappier' and while it can be done by 'tricks' it is certainly an area of study. Also you want to access your data faster and quickly do what you need. Sometimes it means you can do more - in games you have 0.017s to do everything and the faster you are the more candies you can put.

Answer 5

It is an interesting discussion. And we have a few things to look at here.

1. The theoretical computer science - This is an evolving science which means as time goes on we will find new and better ways to solve problems, which means improved algorithms for searching and sorting for instance.

2. Larger communities / larger libraries - Because a lot of work has been done by other people we can just build on their work and use the algorithms they have already created and even coded. And these libraries will be updated with time allowing us automatic access to more efficient programs/algorithms.

3. Development - Now here we have a problem I think. A lot of programmers are not computer scientists so they write code to solve business problems not technical / theoretical problems and would be as happy using a bubble sort as a quick sort for instance. And here the speed of hardware is allowing bad programmers to get away with using bad algorithms and bad coding practices. Memory, CPU speed, storage space these things are no longer major concerns and every few months things are getting larger, faster and cheaper. I mean look at the new Cellphones. They are now more advanced than the mainframe computers / servers from the 1970's / 80's . More storage, more processing power, faster memory.

4. UI & DATA - User Interface/ User Experience and DATA are now considered more important than super efficient code in most areas of development. So speed only becomes and issue when a user has to wait long. If we give the user a good look and feel and he gets good response from the application he is happy. And if business knows all data is stored safely and securely and they can retrieve it and manipulate it at anytime they do not care how much space it needs.

So I would have to say it is not that efficient programmers are no longer important or needed, it is just that very few companies/users reward people for being super efficient programmers, and because of the hardware being better we are getting away with being less efficient. But there are at least still people out there focusing on efficiency and because of the community spirit everyone in time gains benefit from this.

Answer 6

Some other angles on this interesting and deep question that emphasize the interdisciplinary and crosscutting aspects of the phenomenon. Dai quotes Wirth's law in his answer:

Software is getting slower more rapidly than hardware becomes faster.

There are interesting parallels of this idea to phenomena observed in economics. Note that economics has many deep connections with computer science e.g. in say scheduling where scarce resources (say threads etc.) are allocated on request, by "load-balancing" algorithms. Another example is what is called a producer-consumer queue. Also, auctions.

Also e.g., List of eponymous laws, Wikipedia:

Parkinson's law – "Work expands so as to fill the time available for its completion." Coined by C. Northcote Parkinson (1909–1993), who also coined its corollary, "Expenditure rises to meet income." In computers: Programs expand to fill all available memory.

There is some strong similarity also to Jevon's paradox which was observed in the increase in energy use after the more efficient Watt steam engines began to replace the Newcomen design, but use or proliferation of the engines increased:

In economics, the Jevons paradox (/ˈdʒɛvənz/; sometimes Jevons effect) is the proposition that technological progress that increases the efficiency with which a resource is used tends to increase (rather than decrease) the rate of consumption of that resource.

The analogy is that hardware is the resource and software is like the consumption of the resource (aka, supply vs demand). So software and hardware (and advances in each) exist somewhat in a tightly-coupled symbiotic feedback loop with each other, in a sense, coevolving. There are many complex and interrelating factors influencing this interplay, e.g.:

• Coevolution
• Evolutionary race
• Moore's law
• Proliferation of programming languages/structures
• Relative algorithmic vs hardware speedups

Answer 7

No, mostly while considering space complexity! Storage capacity of a normal computer is growing exponentially.