Content deleted Content added
Groupthink (talk | contribs) m →Question about super-exponential growth: fixing wikilink |
Groupthink (talk | contribs) m →Question about super-exponential growth: fixing wikilink again |
||
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? [[User:Navigatr85|Navigatr85]] 21:33, 7 July 2007 (UTC)
:Here's the problem with trying to define something as <math>\mathrm{O}\left (\frac{1}{b-n}\right )</math> – your Big-O upper-bound has to be [[Monotonic function|monotonically increasing]] beyond a certain point where n > n<sub>0</sub>. If you argue that n<sub>0</sub> is less than b, then you get a big old discontinuity when n = b and your function no longer has the required ordering property. If you argue that n<sub>0</sub> is greater than b, then you have a valid ordering property, but negative run-times, which would be [[undefined]].
| |||