I was recently doing some problems on two pointers when I saw some really clever ways to use two pointers on some problems which would otherwise seem impossible to solve faster than O(n^2) complexity. So, that's when I got this thought in my mind, how do we "know" that a particular complexity is the best possible for a particular problem and that there is not a better solution possible using some clever technique that we just haven't thought of yet. For example, let's say that there is some problem which could be solved in O(n^5) time. How do we know that there isn't any n^4 solution that we just haven't discovered yet. Can we just look at any problem and surely say that yes, it cannot have a solution which is better than this particular time complexity? I would be glad if anyone could provide some insight on this topic.
