[supernewton]

Sure, but in practice there don't really seem to exist "natural" problems that are both in P and are worse than O(n^3) or so.

By "natural" I mean a problem that one would actually want to solve, not some contrived problem specifically to make it O(n^100) since that's obviously easily possible.