Content deleted Content added
SandyGeorgia (talk | contribs) small |
Groupthink (talk | contribs) m →Question about super-exponential growth: adding to my comment |
||
Line 139:
: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). See [[Computational complexity theory#intractability|intractability]] for more info. [[User:Groupthink|Groupthink]] 00:03, 8 July 2007 (UTC)
| |||