  The advantages of adaptivity and feedback are of immense interest in signal
processing and communication with many positive and negative results. Although
it is established that adaptivity does not offer substantial reductions in
minimax mean square error for a fixed number of measurements, existing results
have shown several advantages of adaptivity in complexity of reconstruction,
accuracy of support detection, and gain in signal-to-noise ratio, under
constraints on sensing energy. Sensing energy has often been measured in terms
of the Frobenius Norm of the sensing matrix. This paper uses a different metric
that we call the $l_0$ cost of a sensing matrix-- to quantify the complexity of
sensing. Thus sparse sensing matrices have a lower cost. We derive
information-theoretic lower bounds on the $l_0$ cost that hold for any
non-adaptive sensing strategy. We establish that any non-adaptive sensing
strategy must incur an $l_0$ cost of $\Theta\left( N \log_2(N)\right) $ to
reconstruct an $N$-dimensional, one--sparse signal when the number of
measurements are limited to $\Theta\left(\log_2 (N)\right)$. In comparison,
bisection-type adaptive strategies only require an $l_0$ cost of at most
$\mathcal{O}(N)$ for an equal number of measurements. The problem has an
interesting interpretation as a sphere packing problem in a multidimensional
space, such that all the sphere centres have minimum non-zero co-ordinates. We
also discuss the variation in $l_0$ cost as the number of measurements increase
from $\Theta\left(\log_2 (N)\right)$ to $\Theta\left(N\right)$.
