Hash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).