Consequences/existence of problems without any "optimal" algorithm Let $P$ be some kind of "problem" such as addition or graph coloring, that has an input size $n$. Let $S_P$ denote the set of algorithms $A_1, A_2, \dots$ which deterministically solve $P$. Based off this, let $S'_P$ denote the set of "optimal" algorithms that solve $P$, in other words: 

$$S'_P :=  \{A_i ∈ S_P | \nexists A_j ∈ S_P  \textrm{ s.t.} \lim_{n \to \infty} \frac{O(A_i)}{O(A_j)} = 0 \}$$

Is there an example of a problem when $S_P$ is non-empty, but $S'_P = \emptyset$? Also, are there any significant implications concerning the existence/non-existence of such a problem?
Blum's speedup theorem, proved in 1967, shows that there is such a problem $P$ that has no optimal algorithm.

The problem $P$ doesn't look all that much like addition or graph coloring - it's defined in terms of sets of machines $Z_i$, the primitive recursive functions $\phi_i(n)$ computed by the $i$th machine, and "step-counting functions" $\Phi_i(n)$ (which count how many steps the $i$th machine took to execute its function), and involves search over the latter in order to achieve the desired properties :).

It's a good reminder that the space of algorithms is large and counterintuitive - especially when the inputs and outputs are themselves programs. But you're also not likely to see this sort of weirdness until your inputs are programs, either, and maybe not even then depending on what you're trying to do with them...

Reference:

Blum, Manuel. "A machine-independent theory of the complexity of recursive functions." Journal of the ACM (JACM) 14.2 (1967): 322-336.