A circuit with a fixed number of (binary logical) gates can be solved in constant time, as it will have a fixed number of input bits, so brute force will have a fixed number of input options to consider. This does apply to cryptographic algorithms with a fixed key size, like the ones used in practice, as well. The whole point of computational complexity is to look at the scaling behavior when you increase the inputs/key size/size of the circuit.

From my reading no. Because brute forcing anything symmetrical is already O(n). What protects us is the assumption that there is not enough energy in the observable universe to brute force 2^256 key.