Number of terms in Balanced boolean functions? I know that balanced boolean functions are required for creating S-boxes. I want to create four balanced Boolean functions for 4X4 Sbox and as far as I’ve understood, the maximum order of the balanced Boolean function should be &lt;= (number of var)/2. 

But… how many terms should there be in my boolean functions?
In general, if the algebraic normal form representation has few terms, an implementation can be faster.But such a simple representation can also lead to certain attacks.

You can represent such an Sbox as a mapping from $GF(2^4)$ to itself as well as a univariate polynomial mapping from $GF(2)^4$ to itself and what's sparse or simple in one representation can be complex in the other.

There are criteria such as resilience to consider as well, which may be the reason about your comment on nonlinear order.

Saarinen has a nice paper on classifying 4x4 Sboxes here.