Need help to derive the Complexity!
If $m &gt; 0$ is even then the two parties communicate $m/2$ times at their first round of communication. If $m &gt; 1$ is odd then they communicate $(m-1)/2$ times at their first round of communication. In particular, the communication complexity is not $O(\log m)$, but at least $\Omega(m)$. In fact, it is also $O(m)$, but you'll have to figure out why yourself.