Hint: Don't ever work for or hire anyone who would exploit the ambiguity of the English language in a hastily written comment to gain the false appearance of geeky superiority. (Exercise: how would you interpret the situation referred to in the comment to wind up with O(n^2) and how you interpret it to wind up with O(n^3)?)

People like to boast about how important it is to know these kinds of complexities, but in reality they just use mental heuristics to come up with them (which is how we got n^2 and exp(n) from my manager).

For string concatenation, is it important they know how to do it in a linear fashion? Or is it important that they can actually calculate the complexity? Or do you want an in-between where it is OK that they do not really know the complexity, but can tell you that it is definitely super-linear?

I've seen people be fussy that they should be able to explain why it is n^3 (or n^2 or whatever), in a somewhat rigorous fashion. I say "somewhat" because when I then turn to them and ask them to derive the exact expression (not just in big-Oh notation), they will usually fail. Then they will go through hoops trying to explain why it is important to know it in big-Oh notation but not all that important to be able to derive the exact formula.

(There is, of course, a camp that does not believe much in big-Oh and actually prefers to know the leading constant, etc. My example is not contrived.)

I find people will nitpick to their level of granularity, and it is always easy to come up with some justification for their level of preference. But to others, it is just nitpicking.

For me, it is important to know that this is super-linear, whereas one can do it linearly. I don't care if the candidate knows it is n^3 or n^2. That is also why I did not point out my manager's error at saying it is exp(n).