Comment by mockerell

It is indeed very interesting. For the latter the concepts from fine-grained complexity and average time are interesting. For specific problems, there are theoretical fine grained lower bounds for time complexity (i.e. cannot be solved in (truly) subcubic time). However, these rely on assumptions that are even stronger than P != NP.