This all presupposes that reducing big oh increases code complexity. In my experience, that's simply not true. Unless you are writing C without libraries, you are almost certainly dealing with a language rich in datastructures that easily reduce big oh notation while clearly communicating intent.
A dictionary will generally beat storing values as key/value in a list, de-duplicating and linearly searching on the key. If you don't believe that, then go ahead and pollute your codebase with List<Pair<Key, Value>>. See how fast that will be.
Heck, go ahead and use and manage a Pair<Key, Value>[]. After all, can't prematurely optimize by using a data structure that automatically manages growth.
Maybe just store everything as a giant String. You can just keep concatenating new values and searching for others in it. Why let those pesky types get in the way of easy to understand string manipulation and regexs? After all, don't prematurely optimize.
Hey, perhaps you should always just bundle and distribute perl with your applications and fork off new instances of perl since it has such nice regex capabilities. After all, don't prematurely optimize.
Have you measured that performance? Halt before you say it's a bad idea, because obviously we need to profile everything and make sure that starting new perl processes are actually slow. Can't be prematurely optimizing.