News for hackers. Stuff that matters.
Re:Wolfram Rule 30 Prizes by anderskaseorg on Tuesday October 01, 2019 @10:55PM (#21133117)
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.)

Re:Wolfram Rule 30 Prizes by AlEinstein on Thursday October 03, 2019 @08:15AM (#21146089)
Would 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?