Weird, we didn't get into complexity theory until CS 350. Before that we mostly focused on logic, data structures, and languages (with a bit of computing thrown in). This was at Portland State in the late 2000s though.