Formally proving no algorithm exists
See this lower bound for sorting, for example:
http://planetmath.org/lowerboundforsorting

You typically need to assume something about the algorithm's access to the input data. In this case, the assumption is that the algorithm sorts via pairwise comparisons. Any such algorithm must make at least $\Omega(n\log n)$ such comparisons. This is because the pairwise comparisons effectively induce a binary tree on $n!$ leaves -- one leaf for each possible input ordering. Such a tree must have depth $\Theta(\log(n!))=\Theta(n\log n)$.

Note that in a different data access model, algorithms can achieve linear-time sorting:
https://en.wikipedia.org/wiki/Radix_sort

Obiously, faster than linear time is impossible, since you have to at least read all of the inputs.