No Minimum-Time Algorithm?

  • Thread starter mXSCNT
  • Start date
  • #1
315
1
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 on No Minimum-Time Algorithm?

Replies
2
Views
2K
  • Last Post
Replies
1
Views
692
  • Last Post
Replies
1
Views
485
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
934
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
838
  • Last Post
Replies
3
Views
175
  • Last Post
Replies
2
Views
2K
  • Last Post
2
Replies
26
Views
19K
Top