Do we really need efficient algorithms?

Question

I'd like to ask why people devote their time to research algorithms and their efficiency so extensively when computers nowadays are so fast.

Trying to come up with an answer I thought that maybe my assumption is short-sighted, because computers are indeed fast nowadays, but there wouldn't be so fast if we haven't researched the algorithms in the first place - there are probably some low-level algorithms that computers rely on like those responsible for computation, etc.

But I can hardly imagine a real world situation in which it matters if I can multiply matrices in O(n^2.81) (Strassen Algorithm) than in O(n^3). Do computer scientists and mathematicians research such algorithms just for fun/out of curiosity/so they have an original dissertation topic or are there really some real life situations in which naive algorithms are too slow and we need a more efficient one?

Answer 1

TL;DR O(n^2.81) may seem like a small gain compared to O(n^3), but as the data set grows that differences becomes very big, very fast.

How do you feel when a web page takes 5-6 seconds to load up instead of 1-2 seconds? How about if Google Maps took 20-30 seconds to come up with the best route instead of 5-10 seconds?

Think about what happens when traveling a great distance in space and you are off by 1 degree. Every small amount that you are off can drastically increase how far off target you are. The further you need to go the farther off target you will be.

Efficient algorithms are important when dealing with large amounts of data. Something that grows exponentially will grow incredibly fast. The higher the exponent the faster the growth. When dealing with billions of records this begins to really matter.

For smaller data sets preemptively optimizing is considered a bad thing. You are supposed to wait until you see where the program is using the most processing time and optimize that code (see the 80-20 rule).

Also take a look at merge sort over something like bubble sort to notice the massive difference between an efficient algorithm vs. an inefficient one.

Answer 2

Do computer scientists and mathematicians research such algorithms just for fun/out of curiosity/so they have an original dissertation topic or are there really some real life situations in which naive algorithms are too slow and we need a more efficient one?

Efficiency is key not for fun or for curiosity but to be able to solve problems faster in computer science more often than general software development.

Though it is true that computers are fast enough to do computations O(n) like:

List x = [1,2,3,4,5,6]
print [i for i in x]

Sometimes when we have algorithms that have complexity like O(n^2) or even O(n log(n)) we face issues of scalibility. When the data-set we are iterating through or doing any computation on expands, it takes more time to compute. So if we can find algorithms that can reduce time complexity from say O(n) to O(log n), we are able to see a bigger difference on larger data sets.

See this for example:

We want to try and get algorithms as close to the green-areas as possible.

One big reason that complexity is a big topic in computer science is because of the complexity classes P and NP and attempting to prove if P = NP, which may not seem like a big deal in context of programming; but becomes a huge deals with concepts like cryptography.

For a real-life scenario, let's take the travelling salesmen problem which is O(2^nn^2). This problem is not solvable in polynomail time (P) and so belongs to the class of NP problems because there isn't yet an algorithm to solve it in P. However, if there is research and a solution to it being solved in P then there are a lot of implications of it that we can apply to other algorithms.

It's also worth having a look at sorting algoritms for instance bubble sort has a complexity of O(n^2), while we have found better algorithms for sorting like Heapsort which has worst case O(n log(n)).

Answer 3

There are plenty of real-life situations where these optimizations are wanted, all kinds of simulations (nuclear, astronomy, medicine, physics, ....) come to mind first.

And what about simple productivity gains because the spreadsheet calculates 10 seconds faster, the video renders in 3.5 hours instead of 4, the bank processes its millions of transactions 15 minutes faster, etc?

And there are the 'non-productive' gains, like your video game being fast enough so that the execution of your commands now lags only 0.2 seconds instead of 0.4.

Any CPU/GPU core running over 90% utilization (not even continously) is proof that we want more.

Answer 4

Many real-world optimization problems are limited by how much CPU time you are willing to devote to them. In some cases you can do your heavy crunching in a batch mode so it's less of an issue but that's not always an option. Real world example: We have a list of desired parts, we have a piece of wood to cut them from with defects at locations A, B & C. How do we get the best likely outcome? (No perfect answer is possible as we haven't seen the rest of the wood yet.) There's something like two seconds from when the camera has finished analyzing the wood to when the wood is ready to be pushed into the saw--if you take longer than that you are idling a $60k piece of equipment.

Meanwhile, when the machine is cutting up 6 figures worth of wood a year even a tiny improvement in the accuracy of your prediction is worth a lot.

Answer 5

A great deal of complexity research is indeed more mathematical than practical. Often one can get more benefit from a "less efficient" algorithm than from a "more efficient" one. Would you rather multiply matrices in 10^3 milliseconds or in 1000000 × 10^2.81 milliseconds?

There is also the fact that in many cases it is preferable to have an algorithm that obviously works rather than one whose working depends on a long, complex and delicate proof. It is just one less thing to worry about.

So often it is better to improve the constant factor, by parallelism or simply better design at the code level.

But on the other hand if you are dealing with a matrix with a million rows and columns, the power of n starts to have real significance and n^2.81 more complicated steps may take less time than n^3 simple ones.

Answer 6

Efficiency is more important than ever precisely because computers performance have improved! Hardware have become faster, but at the same time the available memory and bandwidth have increased just as much.

Since we tend to use the available resources, a processor will need to do 10x as much work if memory is increased 10x. If you perform an O(n) operation over the available memory, then it will take the same time if both processor speed and memory is increased 10x. But if the complexity is worse than O(n), then the operation will become a lot slower if both processor and memory is increased 10x.

So efficient algorithms actually becomes more important, the more the performance of our computers are improved.

Answer 7

Lots of software would be brought to the knees. If you just change dictionary access to a linear instead of constant time. Change your graphics algorithms to draw one pixel at a time, and your computer just dies.

No computer is fast enough to handle code that is bad enough.