Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have read some complexity papers in which "for infinitely many input sizes" is used.

What is the difference in the computational complexity context between "for infinitely many input sizes" and "for all input sizes"?

share|improve this question

migrated from cstheory.stackexchange.com Feb 17 '13 at 1:11

This question came from our site for theoretical computer scientists and researchers in related fields.

    
Without a concrete example, "infinitely many input sizes" does not make a lot of sense to me. "Almost all", on the other hand, would. –  Raphael Feb 17 '13 at 10:01
    
@Raphael With unary encoding, imagine an algorithm running in linear time on composite numbers, but in superlinear time on prime numbers. Had it been finitely many primes, this algorithm would run in linear time. –  Pål GD Feb 17 '13 at 11:52
    
@PålGD: We don't usually assume unary encoding, but that's not important here. I get the point, thanks for the example; I did not think of piecewise-defined runtimes. –  Raphael Feb 17 '13 at 11:58
add comment

2 Answers 2

up vote 10 down vote accepted

"for infinitely many input sizes $n$, $P(n)$ holds" means there are input sizes $n_1$, $n_2$, $\ldots$, (infinitely many) such that $P(n_i)$ holds for all $i$. In other words, for every integer $k$, there is an input length $n \geq k$ such that $P(n)$ holds.

In contrast, "for all input sizes, $P(n)$ holds" means that for every input size $n$, $P(n)$ holds.

Typically, "for all input sizes, $P$ holds" and "for almost every input size, $P$ holds" are used interchangeably, although the latter technically means that there is a $k$ such that for all input sizes $n \geq k$, $P$ holds. (Note that the negation of "for infinitely many input sizes, $P$ holds" is "for almost every input size, $\neg P$ holds.") This is generally because in the models of computation being considered, constant factors don't matter, so from an "almost every input size" statement you can generally hardcode the solutions for all inputs of length less than $k$ in your model, and get a "for all input sizes" statement.

share|improve this answer
add comment

"For infinitely many input sizes" makes sense in many contexts. For example, when considering the running time of a TM, it may be the case that for all odd-sized inputs, the machine trivially rejects (e.g. if it's an illegal encoding of an instance). In this case, the runtime of a machine can be long only for even sized inputs (from which there are infinitely many), and we take the latter as the over-all runtime (and with some abuse, we may even consider it as $\theta$ of the runtime).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.