Content deleted Content added
Navigatr85 (talk | contribs) |
Navigatr85 (talk | contribs) |
||
Line 136:
== Question about super-exponential growth ==
I was wondering something, just out of curiosity. (I apologize if this is an in appropriate use of this talk page.) I was reading about [[hyperbolic growth]], and I was wondering if any algorithm has been discovered whose run time grows hyperbolically. In other words, the runtime would be something like
<math>\mathrm{O}\left (\frac{1}{b-n}\right )</math>, where b is a positive integer, and n is the length of the input. This would mean that, when n=b, the problem requires an "infinite" number of steps, and is therefore undecidable. But for n<b, the problem would be decidable in a finite number of steps. Actually, now that I think about it, this is an inappropriate use of big-O notation, because big-O notation, in complexity theory, is defined in terms of limits at infinity. But still, are there any problems that are decidable for small inputs, but undecidable for sufficiently large inputs? Navigatr85 21:33, 7 July 2007 (UTC)
| |||