Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.
Let $[n]=\{1,2,\dots,n\}$.
If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position.
If $B\subseteq [n]$, then $\Bbb 1_B$ be the length $n$ vector with $1$s only in positions marked by $B$.
If $i\in[n]$ and $x\in\{0,1\}^n$, let $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.
If $B\subseteq [n]$ and $x\in\{0,1\}^n$, let $x^{B}=x\oplus\Bbb 1_B$ where $\oplus$ is $XOR$ operation.
Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$
Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$
Block Sensitivity of $f$ at input $x$, $BS_x(f)$ is maximum $r$ such that there is a set of disjoint subsets $\{B_i\}_{i=1}^r$($\forall i\neq j$, $B_i\cap B_j=\emptyset$) such that $$\forall j\mbox{, }f(x)\neq f(x^{B_j})$$
Block Sensitivity of $f$ is $$BS(f)=\max_xBS_x(f)$$
Given $f$ in $n$-variables, would it be reasonable to ask the complexity class of deciding $S(f)>c$ and $BS(f)>c$ for a fixed $c>0$? I understand that describing a Boolean function takes $2^n$ bits fully.
Does computing $BS(f)$ also take $O(2^{n+\epsilon})$ time as in answers below?