Currently studying asyptotic analysis and cryptography.
For a key of n length (of binary bits) we have been asked how many permutations we would have to try for a 1% chance of cracking the key (using brute force).
I'm a bit stumped because we don't know the possibility space. Ofc, there are 2^n possibilities so is it simply (2^n)/100??
Yes, that is exactly right. In this problem, it is tempting, but unnecessary, to consider event by event (i.e. failure by failure) how the probability changes.
That is, one approach is to assume that your first guess is wrong. The probability of this happening is $~\dfrac{2^n -1}{2^n}.$
Then, with only $2^n - 1$ possibilities left, the probability of the second guess also being wrong is $~\dfrac{2^n - 2}{2^n - 1}.$
This implies that the probability that the first two guesses are both wrong is
$$\frac{2^n - 1}{2^n} \times \frac{2^n - 2}{2^n - 1} = \frac{2^n - 2}{2^n}.$$
However, the above approach is over-kill. Instead, you can pretend that you have a sequence of $2^n$ elements, and that a user chooses one of the elements at random.
Then, you can pretend that these $2^n$ elements are jumbled into a random order, and that you are then going to select only the first $(100)$ elements of the jumbled sequence, one at a time.
Then, you will crack the password if and only if the password is one of the first $100$ (random) elements in the random sequence of $2^n$ elements.
So, your probability of cracking the password is $~\dfrac{100}{2^n}$ and your probability of not cracking the password is $~\displaystyle 1 - \frac{100}{2^n} = \dfrac{2^n - 100}{2^n}.$