This is a general question about the practical use of computational complexity in security. Wikipedia has a good article about the theoretical background of computational complexity. In the course of conversation with colleagues, a topic that is brought up occassionally is the security of any algorithm in relation to the security of any other algorithm, and I would like to make sure I have an accurate understanding of computational complexity for these situations.

Suppose I have an encryption algorithm like AES that can use a 256-bit key. My understanding is that the computational complexity would then be 2^256 for a brute force attack to recover the key. A "crack" of the algorithm would be anything that can reduce this complexity to less than 2^256. It would seem to make sense that this means a program would have to guess a maximum of 2^256 passwords before it has guessed every possible key, and therefore should have gained access at some point along the way. Is this the correct way to think about computational complexity in this context?

To explain my line of thinking in an example: While reading about the 256-bit AES "crack" published a few months back, one of the things I remember was that while the computational complexity of guessing 256-bit AES keys could be reduced to 2^119, this additionally required a size complexity of 2^119. (To my understanding, the size complexity of brute force attacks on any algorithm can be as low as 1 -- one key is guessed, rejected, and iterated at a time, so only storage space for one key is necessary since that space is re-used for each key.) My understanding of a "size complexity of 2^119" is that 2^119 keys need to be stored at one time in order for the attack to work. Given this, if I assume a key length of 256 bits and I need to store 2^119 keys simultaneously, I should be able to calculate the total storage size required to make an attempt at this particular attack:

In bits: 256 bits * 2^119 = 1.7 * 10^38 bits (rounded)

Converted to terabytes: 1.9 * 10^25 terabytes (rounded)

My question is this: When someone says "computational complexity" and "size complexity" in relation to the strength of an algorithm, am I thinking about the meaning correctly from a practical perspective?

Thanks for the help.