Quite a simple question though I can't wrap my head around it:
The key size is: $n$
Because it's brute force it tries each possible key once from $0$ to $n$, but in my head that just makes the run time $O(n)$, though it's surely meant to be a polynomial or exponential. The decryption message is of size $x$ though I'm not sure it is relevant. Would it be because the key is of size $n$, but they must also try all keys from $0$ to $n$ make it $2^n$?