Change the x that the big O is about, for example by using vector instructions.

Implement a theoretically less efficient algorithm that is faster (examples: switch to a O(n^2) sort for small data set, or to a linear search for smallish arrays)