[eveningcoffee]

Pretty much spot on and that was my point. You can answer to this question, you know what is complexity class, you know that it is a negative example and it is rather bad.

See, I am not a recruiter or interviewer, but this question feels to me like an useful one to prune out ignorant fools who start to lament how unfair is to ask such questions instead of giving more or less correct answer.

Naturally if short direct answer is the only accepted answer and there is no way to discuss these things with the interviewer then I would also walk away.