[Solved]: Is it possible to decide if a given algorithm is asymptotically optimal?

Here is a simple argument to show that they are undecidable, i.e. there are no algorithms to check if a given algorithm is optimal regarding its running-time or memory usage. We reduce the halting problem on blank tape to your problem about running-time optimality. Let $M$ be a given Turing machine. Let N be the following Turing machine: $N$: on input $n$
1. Run $M$ on blank tape for (at most) $n$ steps.
2. If $M$ does not halt in $n$ steps, run a loop of size $2^n$, then return NO.
3. Otherwise, return YES. There are two cases:

1. If $M$ does not halt on blank tape, the machine $N$ will run for $Theta(2^n)$ steps on input $n$. So its running time is $Theta(2^n)$. In this case, $N$ is obviously not optimal.
2. If $M$ halts on blank tape, then machine $N$ will run for constant number of steps for all large enough $n$, so the running time is $O(1)$. In this case, $N$ is obviously optimal.

In short: $$M text{ halts on blank tape } Leftrightarrow N text{ is optimial }$$ Moreover given the code for $M$ we can compute the code for $N$. Therefore we have reduction from halting problem on blank tape to running-time optimality problem. If we could decide if a given Turing machine $N$ is optimal, we could use the above reduction to check if a given machine $M$ halts on blank tape. Since halting on blank tape is unecidable your problem is also undecidable. A similar argument can be used for space, i.e. it is also undecidable to check if a given Turing machine is optimal regarding the space it uses. Even a stronger statement is true: we can’t decide if a given computable function is an upper-bound on the time complexity of computing a given computable function. Similarly for space. I.e. even basic complexity theory cannot be automatized by algorithms (which can be considered a good news for complexity theorists ;).