Computing the nth cell clearly takes at least 1 time unit, and by the definition of O(), we have 1 = O(n). I’ll be claiming my $10,000 now.
(More seriously, don’t confuse O() with Ω() and Θ(), folks: https://en.wikipedia.org/wiki/Big_O_notation.)
(More seriously, don’t confuse O() with Ω() and Θ(), folks: https://en.wikipedia.org/wiki/Big_O_notation.)
For example, say that someone shows that the most efficient algorithm for computing the value (0 or 1) of the central column of the nth row of rule 30 starting with a single 1 cell (i.e., the system under consideration for the prize) takes time n^2. Wouldn’t one then say that the complexity of the calculation is O(n^2)? One couldn’t say that it’s O(n), surely?