Just like @Peter, I also begin computational complexity when I introduce sorting and searching. I touch back upon it at various times throughout the year.
(Even though the topic is not part of the AP Computer Science A curriculum, I present the concepts within that course.)
It's important to note that we don't go into great depth; my main learning target is to give them an intuitive sense of constant, logarithmic, linear, and quadratic growth.
During my first sorts/searches lecture, I have them figure out the $O$, $\Omega$, and $\Theta$ (where applicable) for every sort I present. We do, in order:
- Linear search
- Binary search
I use these two to introduce the concept of algorithmic efficiency and those three functions, and the shortcuts we can take when we figure them out $O$.
Then they practice on the following sorts:
- Bubble Sort
- Insertion Sort
- Selection Sort
Later on, when we do a maze solver, I touch on algorithmic complexity again, and yet again when we look at mergesort (after we have done recursion). And yet again when we talk about adding and removing elements from the front and back of linked lists and array lists. (There is actually quite a bit of practice in this exercise)
I have found that, with one lecture and a bit of practice spread throughout the year, the students seem to pick up the concept well.