This whole thing is part of the circular logic problem with hiring: you have people making these hiring decisions that aren't trained in hiring, so they just go with "what makes sense to them" or hiring a younger version of someone who looks exactly like them for a junior role. It's fine, it works for the company, but it's why people will miss long term talent.
When you make the switch from writing code to support UI elements to writing code to handle data processing, for example, you're going a bit beyond the standard coding bootcamp's toolkit. I think this is the author's point, and why he recommends that bootcamp grads (who may end up in situations like these) take extra steps to be prepared for whatever curveballs come their way in their careers.
I think it's important that bootcamps teach about complexity, and that they don't do a great job of it. I also think asking anyone to speak in terms of big o may or may not be the most comfortable way for the candidate to talk about it.
I do a lot of interviewing now, and prefer to check to make sure that they understand how to optimize their solutions in a coding context, rather than asking about the "description" of that optimization, personally.