No Minimum-Time Algorithm?

  • Thread starter mXSCNT
  • Start date
  • #1
315
1

Main Question or Discussion Point

I was just wondering. Is there a computational problem P for which there is no asymptotically least-time solution?

In other words: let x be an algorithm which is a solution to P. Denote by T(x), the worst-case runtime of x as a function of its input size. Is it possible that for any algorithm x that solves P, there exists an algorithm y that solves P, where T(y) = o(T(x))?

o is little-o notation, so in other words that would mean T(y) = O(T(x)) and T(y) is not Θ(T(x)).
 

Answers and Replies

  • #2
10
0
Well, there are algorithms that take time O(ln(x)). Does that count? You just want something that is faster than linear, or do you want something that isn't asymptotic to ANYthing? What are you after? O(ln(ln(ln .... forever .... (x)))))....)? That wouldn't even make any sense. Take the log enough times and eventually you get a negative number, and you take it again, and poof.
----
edit:
holy cow, I didn't notice what date this was written. The thing just showed me a bunch of related posts and I was perusing them.
 

Related Threads for: No Minimum-Time Algorithm?

Replies
2
Views
2K
  • Last Post
Replies
1
Views
599
  • Last Post
Replies
1
Views
399
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
829
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
726
  • Last Post
Replies
2
Views
2K
Top