# Question about brute force running time

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$$?

When we say key size is $$n$$, we consider $$n$$ in bits, n-bit key size. For example, AES has 128, 192 and 256-bit keys sizes. Therefore, we have $$2^{128}$$ key to search for AES-128 and that is exponential, $$\mathcal{O}(2^n)$$
In cryptography, we use also a security parameter that measures the input size of the problem. The security parameter is represented as unary representation ( $$\lambda-\text{times }1)$$ so that the complexity of the cryptographic algorithms will be polynomial time.
For RSA like systems, when we say the security parameter is $$1^\lambda$$, the $$\lambda$$ represents the number of bits of RSA modulus $$n$$. So the positive integer $$n$$ must be between $$0,\ldots,2^{\lambda-1}$$.