That argument could also be used to say that the FFT's time complexity of O(n log n) should be impossible.