How are lookup tables described from the perspective of complexity theory?
Lookup tables take a key, and either provide a value according to the key or tell you that there is no value under this key. 

Time and space requirements will depend on the implementation. It's usually not further mentioned if it is obvious what kind of implementation a reasonable person would use.