Content deleted Content added
Navigatr85 (talk | contribs) |
Groupthink (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)
: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]].
:However, not every algorithm is boundable with a Big-O limit (see [[run-time analysis]]), and there are undecidable algorithms (see [[halting problem]]). Unfortunately, I do not know if there are algorithms that are decidable for small inputs but undecidable for large inputs – but I can tell you that there are algorithms whose run-times grow extraordinarily rapidly as n increases, such that the fastest supercomputers in existence would take until the end of the universe to solve problems for sufficiently large inputs (see [[Ackermann function]] and [[busy beaver]] for examples). [[User:Groupthink|Groupthink]] 00:03, 8 July 2007 (UTC)
| |||