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