No Fastest Algorithm: Examples & Explanation

  • Thread starter Dragonfall
  • Start date
  • Tags
    Algorithm
In summary, there is no fastest algorithm for multiplication, but there are many algorithms that can solve the problem. Coppersmith and Winograd have shown that there is no fastest algorithm for "Strassen-type bilinear" matrix multiplication. However, it is still possible for there to be a fastest algorithm for other types of matrix multiplication. There are also heuristics that suggest that there may not be a fastest algorithm for certain problems due to the infinite number of possible algorithms. Additionally, the existence of infinite descending chains of slower complexity classes further supports the idea that there may not be a single fastest algorithm for certain tasks.
  • #1
1,030
4
It has been conjectured that there is no fastest algorithm for multiplication, among other things. Can somebody give me an example of something that provably has no fastest algorithm for?
 
Mathematics news on Phys.org
  • #2
Here's a partial answer -- the best I could do at the moment. Coppersmith & Winograd show that there is no fastest "Strassen-type bilinear" matrix multiplication.

D. Coppersmith and S. Winograd, "On the Asymptotic Complexity of Matrix Multiplication", SIAM J. Comput. 11:3 (1982), pp. 472-492.
 
  • #3
But is there a simple problem, even something completely artificial, that shows this CAN happen?
 
  • #4
Matrix multiplication not simple enough for you? Maybe you need to say what you mean by 'simple'.
 
  • #5
Matrix multiplication has not been proven either way, and in fact according to http://arxiv.org/abs/math.GR/0511460, if a certain conjecture is true, then there is a fatest algorithm that's in O(n^2).
 
  • #6
Surely there has to be a 'fastest' algorithm, or at least an algorithm that's joint fastest. Perhaps that's what it means?
 
  • #7
Here are some heuristics on why there might not be a fastest algorithm for something. For any given computable task, there are always infinitely many algorithms to solve it, because you can always add "futile" steps that just waste time, adding to the complexity. Therefore, there always exists an infinite ascending chain of slower and slower complexity classes which contain these algorithms. The question is, is it possible that infinite descending chains also exist?

EDIT: I want something computable, because any uncomputable problem trivially has no fastest solution.
 
Last edited:
  • #9
Oh right I think I see. But since there only a finite number of ways of arranging code, then the fastest algorithm has to exist anyway. Unless you're talking about infinite length of code as well?
 
  • #10
Twinbee said:
Oh right I think I see. But since there only a finite number of ways of arranging code, then the fastest algorithm has to exist anyway. Unless you're talking about infinite length of code as well?

?

The number of finite programs is infinite.
 
  • #11
Dragonfall said:
The question is, is it possible that infinite descending chains also exist?

Of course. The different types of Toom-Cook multiplication are an easy example. Of course there are algorithms that outperform all of them, so they don't satisfy your original question.
 

1. What is the concept of a "fastest algorithm"?

The concept of a "fastest algorithm" refers to the most efficient and optimal way to solve a given problem or complete a task. It is measured by the time and resources required to complete the task, and in computer science, it is often measured in terms of runtime complexity.

2. Is there such a thing as the "fastest algorithm"?

No, there is no single algorithm that can be considered the fastest for all problems. Different algorithms may be more efficient for different tasks or inputs. The concept of the "fastest algorithm" is a theoretical concept used to compare and analyze different algorithms.

3. What are some examples of "fastest algorithms"?

Some examples of algorithms that are considered very efficient and have a relatively low runtime complexity are quicksort, merge sort, and binary search. However, it is important to note that the efficiency of these algorithms may vary depending on the specific problem or input.

4. Why is it not always possible to find the "fastest algorithm" for a given problem?

Finding the most efficient algorithm for a given problem is a complex task and often requires a deep understanding of the problem and the available algorithms. In some cases, it may not be possible to find the "fastest algorithm" due to limitations in computing power or the complexity of the problem itself.

5. How do scientists and researchers compare and analyze different algorithms?

Scientists and researchers use various techniques, such as analyzing the runtime complexity, conducting experiments and simulations, and using mathematical models, to compare and analyze different algorithms. They also consider factors such as memory usage, scalability, and practicality in real-world applications.

Suggested for: No Fastest Algorithm: Examples & Explanation

Replies
5
Views
665
Replies
1
Views
710
Replies
3
Views
3K
Replies
1
Views
508
Replies
4
Views
2K
Replies
4
Views
3K
Replies
3
Views
1K
Replies
1
Views
776
Back
Top