4 ms·
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, d
by anderskaseorg 7y ago
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. https://en.wikipedia.org/wiki/Big_O_notation.)
- AlEinstein 7y agoWould you mind providing a little more detail of your reasoning? 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?