Complexity Analysis - Walkthrough

States: $O(rows \cdot 2^{cols})$. Transitions per state: up to $2^{cols}$ (all ways to fill a row). Total time: $O(rows \cdot 4^{cols})$.

Time complexity: $O(rows \cdot 4^{cols})$.

Space complexity: $O(4^{cols})$. This is exponential in $cols$ but linear in $rows$. improvement: precompute valid transitions. If many transitions are invalid, the actual count is smaller. Matrix exponentiation: if $rows$ is huge, use matrix power in $O(4^{cols} \cdot cols \cdot \log rows)$. Matrix exponentiation helps when the number of rows is huge. The matrix size is the number of valid profiles.