$\epsilon$-approximation Sub-linear time monotonicity testing
Let $P$ denote the number of pairs of indices $i&lt;j$ such that $f(i)=1$ and $f(j)=0$, and let $C$ be the minimal number of flips required to make $f$ monotone. First, we show by induction on $n$ that for every function $f$ defined on $[n]$ it holds that $C^2\le 3P$.
Suppose that the claim holds for $n$ and let $f$ be a function defined on $[n+1]$. We denote by $C(n),P(n)$ the number of corrections and monotonicity violating pairs for $f|_{[n]}$ correspondingly. Finally, let $w(n)$ denote the weight of $f$, i.e. $w(n)=\big|f^{-1}(\{1\})\cap[n]\big|$. Observe that if $f(n+1)=1$ then $C(n)=C(n+1)$ and the claim clearly holds, it thus suffices to focus on the $f(n+1)=0$ case. If $f(n+1)=0$ then $P(n+1)=P(n)+w(n)$ and $C(n+1)\le C(n)+1$. Applying the inductive hypothesis $C^2(n)\le 3P(n)$ we have:
$$C^2(n+1)\le C^2(n)+2C(n)+1\le 3P(n)+2C(n)+1=\\3P(n+1)+2(C(n)-w(n))- w(n)+1$$
Since $C(n)\le w(n)$ and $w(n)\ge 1$ (the claim is trivial for the constant zero function), this concludes the proof.
The above inequality yields a simple algorithm for testing monotonicity. Sample a pair $i&lt;j$ uniformly at random and answer &quot;no&quot; if $f(i)&gt;f(j)$. Let $q$ denote the probability that $i,j$ is such a pair, then $q\ge \frac{P}{n^2}\ge \frac{C^2}{3n^2}\ge \frac{\epsilon^2}{3}$. By repeating this procedure $\approx q^{-1}$ times, you obtain an $O\left(\frac{1}{\epsilon^2}\right)$ algorithm for separating the monotone from the $\epsilon$-far from monotone case.