I'm trying to draw a line between what is considered premature optimization and what isn't. My main concern right now is Big O Notation. If I make a design decision in a C++ application based on Big O Notation (Say I choose O(1) over O(n) complexity), does that make it a premature optimization decision? Where can the line be drawn between what is premature and what is not?

Again, the main question is: Can Big O Notation be considered premature optimization when considered at design time?

All opinions are welcome!