I like to start by thinking about cache locality and ensuring linear layout. Next focus on one-time, or minimal memory allocation. Then there are a bunch of small, systemic things you need to get right. After that you can start worrying about worst case big O scenarios.
Of course this depends on your language. A c programmer will have a different mental model than a python one.