Comment by jkhdigital

No, lookup tables aren’t magic. The lookup table is part of the program and the execution time includes reading the program itself. A table of size 2^n takes O(2^n) to read into memory.