Content deleted Content added
Groupthink (talk | contribs) →Question about super-exponential growth: correction |
Groupthink (talk | contribs) →Question about super-exponential growth: more corrections |
||
Line 138:
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 <s>be [[Monotonic function|monotonically increasing]]</s> (<i>I think that's the case but I'm not certain</i>) apply 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 <s>no longer has the required ordering property</s> is no longer an upper-bound. If you argue that n<sub>0</sub> is greater than b, then you have a valid <s>ordering property</s> upper bound, but for negative run-times
:However, <s>not every algorithm is boundable with a Big-O limit (see [[run-time analysis]])</s> (''I might be wrong about that, too''), 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). See [[Computational complexity theory#intractability|intractability]] for more info. [[User:Groupthink|Groupthink]] 00:03, 8 July 2007 (UTC)
| |||