Comment by david-gpu
11 hours ago
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.
11 hours ago
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).