There's an additional difficulty that maybe could be stressed more: Knowing the computational complexity given the representation of a function as an algorithm is also not trivial.
A low Kolmogorov complexity can still lead to a high runtime
(I'm sure the author is aware of this).