Is There a Problem With No Asymptotically Optimal Algorithm?

[mXSCNT]

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

 

[Sandor]

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.