Why do look up tables speed things up compared to brute force? I'm currently reading up on lookup tables and efficiency. In my uni script it says the following:

For Brute Force:


Preparation time: $O(1)$
Disk space requirement: $O(1)$
Time required to crack the password: $O(2^n)$


Full lookup table:


Preparation time: $O(2^n)$
Disk space requirement: $O(2^n)$
Time required to crack the password: $O(1)$


I'm not sure I'm understanding this correctly. 

As far as I understand, for Brute Force:

$O(1)$ is the time required to look up the password in my table of all possible passwords.
The disk space requirement is simply as large as needed for a list of all possible passwords, so $O(1)$ as well

My questions:

Why is the time needed to crack the password $O(2^n)$? How is it determined?

It seems I don't understand the concept of a lookup table either. As far as I see, a lookup table will simply hash the full list of possible passwords (so required disk space is larger) but what then? Why is the cracking of the password per se faster? 

I think I'm missing something crucial here. Any help will be appreciated.
Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed. 

Now what a brute-force attack does is, given $m$, it takes a starting key $k$, evaluates $P(k,m)$ if it returns false, sets $k\gets F(k)$. This will take $\mathcal O(2^n)$ evaluations of $P$ and $F$. Assuming both can be computed in $\mathcal O(1)$ the entire calculation takes $\mathcal O(2^n)$.

Now for the look-up table. For this you simply start at some key $k$, and store the $m$ such that $P(k,m)$ yields true as a pair $(m,k)$ in a giant array (or hashmap). Now you repeat this with $F(k)$. When you then get a concrete $m$, you simply look it up in the table and find the corresponding $k$. For hashmaps and continuous arrays, this takes time $\mathcal O(1)$ (ie the lookup time is independent of the number of elements). Clearly, you need storage for all the $2^n$ pairs of $(m,k)$. Now the preparation time assumes that you can find $m$ such that $P(k,m)$ is true, but this is usually possible in constant time, e.g. by evaluating a hash function or an encryption cipher.