Comment by jkhdigital
12 hours ago
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.
12 hours ago
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.
You can read the table on demand. If you are only processing n elements with an algorithm that is very roughly nlogn, you would not be reading all 2^n entries of the lookup table.
Yes, but writing down the address in the lookup table takes log(2^n)=n bits, so the claim of an O(1) lower bound is simply wrong.
The transdichotomous models assume a number big enough to hold n can be written in constant time when determining whether something runs in O(n log(n)).
I don't know whether the log of the size of the table needed has a linear relationship to log(n) in this case.
I do not encourage you to look at the diagonalization argument, it has similarly uncomputable elements (that take "longer than infinite" time because they are unconstructable).