Concise way to say "increases with n or some term of n"
"Presumably the complexity of each new connection is an increasing function of the number of rules."

But you don't mean complexity. Problems have complexity, algorithms have running time (or, more generally, resource usage), functions have growth rate.