Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/#!/StackCompSci/status/554935638320222209
Formatting and correction to Landau notation.
Source Link
David Richerby
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be?

For example, lets take the problem of sorting an array.

Many of the simpler sort algorithms have a worst-case efficiency of O(n^2)$O(n^2)$ such as Quick Sort and Bubble Sort. However, there are other algorithms such as Timsort and Smoothsort that have O(n log n)$O(n \log n)$, which is more efficient.

No other algorithm (to my knowledge) has been able to sort an array more efficiently thatthan O(n log n)$\Theta(n\log n)$. Is it possible to prove that no other algorithm exists that is more efficient?

If there is a way to prove for sorting algorithms if an algorithm exists that is more efficient, does this apply to other problems as well?

Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be?

For example, lets take the problem of sorting an array.

Many of the simpler sort algorithms have a worst-case efficiency of O(n^2) such as Quick Sort and Bubble Sort. However, there are other algorithms such as Timsort and Smoothsort that have O(n log n), which is more efficient.

No other algorithm (to my knowledge) has been able to sort an array more efficiently that O(n log n). Is it possible to prove that no other algorithm exists that is more efficient?

If there is a way to prove for sorting algorithms if an algorithm exists that is more efficient, does this apply to other problems as well?

Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be?

For example, lets take the problem of sorting an array.

Many of the simpler sort algorithms have a worst-case efficiency of $O(n^2)$ such as Quick Sort and Bubble Sort. However, there are other algorithms such as Timsort and Smoothsort that have $O(n \log n)$, which is more efficient.

No other algorithm (to my knowledge) has been able to sort an array more efficiently than $\Theta(n\log n)$. Is it possible to prove that no other algorithm exists that is more efficient?

If there is a way to prove for sorting algorithms if an algorithm exists that is more efficient, does this apply to other problems as well?

Source Link
erdekhayser
erdekhayser
  • 253
  • 2
  • 5

Can a Minimum Possible Efficiency be proven?

Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be?

For example, lets take the problem of sorting an array.

Many of the simpler sort algorithms have a worst-case efficiency of O(n^2) such as Quick Sort and Bubble Sort. However, there are other algorithms such as Timsort and Smoothsort that have O(n log n), which is more efficient.

No other algorithm (to my knowledge) has been able to sort an array more efficiently that O(n log n). Is it possible to prove that no other algorithm exists that is more efficient?

If there is a way to prove for sorting algorithms if an algorithm exists that is more efficient, does this apply to other problems as well?