Complexity class of sensitivity
[An alternative answer for $BS(f)$]

There is a paper related to this problem.

Scott Aaronson: Algorithms for Boolean Function Query Properties.
SIAM J. Comput. 32(5): 1140-1157 (2003)

The paper gives an $O(N^{\log_2 5} \log N)$ algorithm for computing $BS(f)$ if $f$ is given by
a truth table of size $N=2^n$. Thus, even if $c$ is not fixed, deciding $BS(f) &gt; c$
is in P.