2

This question already has an answer here:

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?

marked as duplicate by gnat, Robert Harvey, 17 of 26, Erik Eidt, durron597 Sep 20 '16 at 18:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    All you have to do is run any sufficiently bloated program on a modern flame-thrower computer to know that there's a lot of room for improvement in software performance. You don't have to look very far to find such programs, either. – Robert Harvey Sep 20 '16 at 14:40
  • 5
    We have a situation now where competing chip engineers bend over backwards to get higher and higher clock rates, pipelining, memory caching, and so on, to make machines still faster. At the same time, lazy programmers who don't really have any competition write bloated code that can easily be 100s of times slower than necessary. The hardware folks will never be able to keep up with that. – Mike Dunlavey Sep 20 '16 at 14:45
  • 1
    One real-life example I observed first hand: Big-O efficiency of an algorithm used in a particular stage of a compiler made the difference between, say, 30 minutes of compilation time versus 3 minutes. – njuffa Sep 20 '16 at 14:50
  • Which applications for using large matrices do you know? Please clarify. – Doc Brown Sep 21 '16 at 21:05
4

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.

  • 3
    Your answer is not wrong, but IMHO your examples are not well chosen - these are examples where better hardware & network can actually compensate slow implementations. Efficient algorithms become interesting when one needs a fews seconds for getting a result instead of having to wait for 100 years. – Doc Brown Sep 20 '16 at 15:54
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?

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:

enter image description here

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

  • Just an FYI for readers, the green area isn't necessarily faster in real world usage. an n^2 algorithm may perform faster than an O(1) algorithm for data sizes found for a particular application. It's important to keep both sides in mind. – whatsisname Sep 20 '16 at 15:31
  • 1
    Calling O(n) "fair" and O(n*log(n)) "bad" is rather dubious IMO. These are so close together (the base-2 logarithm is almost never bigger than 50) that constant factors decide which is ahead, even for very large problem instances. – CodesInChaos Sep 20 '16 at 15:55
2

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.

2

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.

1

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.

1

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.

  • It's a fundamental law of physics: Nature Abhors a Vacuum :) (I had a laptop once with a huge disk: 30mb. Did a lot of development on that.) – Mike Dunlavey Sep 21 '16 at 21:19
0

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.

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