On the complexity of the realization of Zhegalkin polynomials

We show that the complexity of a Zhegalkin polynomial of degree $k$, $2\le k\le n$, does not exceed
$$ \sum_{i=0}^{k}\binom ni/\log_2\sum_{i=0}^{k}\binom ni(1+o(1)), $$
(as $n\to\infty$) and asymptotically coincides with this number for almost all such polynomials. We also show that the complexity of any homogeneous Zhegalkin polynomial of degree $k$ (for most values of $k$) does not exceed
$$ \binom nk/\log_2 \binom nk(1+o(1)), $$
(as $n\to\infty$) and asymptotically coincides with this number for almost all such polynomials.