The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

Wolfram's rule 30 is a one dimensional cellular automaton. If you want to know the state of the CA at step $t$, given the initial configuration, you just need to run the rule for $t$ steps. At every step the computation consist in no more than a bunch of if's, so the time complexity of such CA is linear in $t$.