Are there any problems that get easier as they increase in size?

Question Detail: 

This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size? I doubt any practical problems are like this, but maybe we can invent a degenerate problem that has this property. For instance, perhaps it begins to "solve itself" as it gets larger, or behaves in some other bizarre way.

Asked By : dsaxton

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51362

Answered By : D.W.

No, it's not possible: at least, not in an asymptotic sense, where you require the problem to keep getting strictly easier, forever, as $n \to \infty$.

Let $T(n)$ be the best possible running time for solving such a problem, where $n$ is the size of the input. Note that the running time is a count of the number of instructions executed by the algorithm, so it has to be a non-negative integer. In other words, $T(n) \in \mathbb{N}$ for all $n$. Now if we consider a function $T: \mathbb{N} \to \mathbb{N}$, we see there is no such function that is strictly monotonically decreasing. (Whatever $T(0)$ is, it has to be finite, say $T(0)=c$; but then since $T$ is monotonically strictly decreasing, $T(c) \le 0$ and $T(c+1) \le -1$, which is impossible.) For similar reasons, there is no function that is asymptotically strictly decreasing: we can similarly prove that there's no running time function $T(n)$ where there exists $n_0$ such that for all $n \ge n_0$, $T(n)$ is monotonically strictly decreasing (any such function would have to become eventually negative).

So, such a problem cannot exist, for the simple reason that running times have to be non-negative integers.

---

Note that this answer covers only deterministic algorithms (i.e., worst-case running time). It doesn't rule out the possibility of randomized algorithms whose expected running time is strictly monotonically decreasing, forever. I don't know whether it's possible for such an algorithm to exist. I thank Beni Cherniavsky-Paskin for this observation.