Conditional expectations algorithm cost

Directly scanning all $m$ edges to evaluate each child of each of $n$ choices takes $O(nm+n)$ elementary operations, in Big O notation. There is a faster implementation. When assigning vertex $v$, let $d_0$ and $d_1$ count its already assigned graph neighbours labelled zero and one. Contributions from edges not incident to $v$ are unchanged, and contributions from edges to unassigned graph neighbours stay $1/2$ for either choice. ThereforeChoose zero if $d_1\ge d_0$, otherwise one: put $v$ on the side with fewer already assigned graph neighbours. With adjacency lists, scanning each vertex's list once costs $O(n+m)$ operations overall and uses $O(n+m)$ storage including the graph. These bounds count operations on labels and counters that fit in machine words of $O(\log (n+m+2))$ bits. Multiplying the conditional expectation cut formula by two also permits exact integer comparisons without rounding.

If $\mathrm{OPT}$ is the size of a maximum cut, then $\mathrm{OPT}\le m$. The constructed cut of a graph thus has size at least $m/2\ge \mathrm{OPT}/2$, an approximation ratio of $1/2$ in the maximization convention. The five-versus-six example illustrates the gap between this guarantee and exact optimization.

For a general randomized algorithm, the averaging proof alone does not establish efficient derandomization. One needs a polynomial number of commitments, an efficient way to find a suitable child at each step, and manageable representations and evaluation costs for the relevant conditional expectations. Those evaluations can themselves be hard. Enumerating all completions verifies this small example, but would take exponentially many assignments as $n$ grows. The polynomial-time algorithm here comes from the local conditional expectation cut formula, not from that enumeration.