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?
What is the difference between for infinitely many n and for all n?
complexity theory;terminology
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.