How to bring attention to computational complexity?
One technique I use for sorting algorithms follows after CS50's demonstrations of the differences among bubble sort, selection sort, and insertion sort. I have 8 students line up in the following order:

4 - 2 - 6 - 8 - 1 - 3 - 7 - 5


Here, 4 represents index 0 of an array of numbers I'd like to sort. I literally walk them through the algorithms, and they can see how much walking I have to do up and down the "array" in order to get it sorted. When it comes time to examine the code for these algorithms, I remark on the use of for loops and how nested for loops lead to $O(n^2)$.

We compare the iterative approach with the recursive approach of merge sort (which certainly could be added to the "walking" demo), which goes back to something we discuss on Day 0 about linear v. binary search. I have students explore this visualization tool. There are also a number of videos on YouTube I draw from that compare algorithms sorting the same data. 

Students also have to complete an assignment called Sort Race, which requires them to implement sorting algorithms and test them against data sets of varying types: reversed, already sorted, all sorted but one, and random. When they see algorithms take a significant amount of time on an already sorted list, they get why it's not the preferred solution and can then go back to the code to see what slows it down (and what doesn't slow down others in some cases).