Upper bound derivation of expected time for finding a large cut
We can upper bound the first summand by
$$
\sum_{i \leq m/2-1} i \Pr(X=i) \leq
\sum_{i \leq m/2-1} (m/2-1) Pr(X=i) =
(m/2-1) \sum_{i \leq m/2-1} Pr(X=i) =
(m/2-1) Pr(X \leq m/2-1) = (1-Pr(X \geq m/2))(m/2-1) = (1-p)(m/2-1).
$$
Similarly, we can upper bound the second summand by
$$
\sum_{i \geq m/2} i \Pr(X=i) \leq
\sum_{i \geq m/2} m Pr(X=i) =
m \sum_{i \geq m/2} Pr(X=i) =
m Pr(X \geq m/2) = pm.
$$