Help with a difficult expected runtime recurrence
Yes, you'll have $B(i) = O(\sqrt{n})$ (with very high probability).

Note that $k_i$ is binomially distributed, so it is approximately Gaussian.  It has mean $0$ and standard deviation

$$\sigma_i = \sqrt{n} \times 2^{-i/2 - 1}.$$

The probability that $k_i$ is more than, say, 10 standard deviations above the mean is incredibly small.  We'll define the event $\textsf{BAD}_i$ to be true if $k_i \ge 10 \sigma_i$, and we'll define the event $\textsf{BAD}$ to hold if there exists $i$ such that $\textsf{BAD}_i$ holds, i.e.,

$$\textsf{BAD} = \textsf{BAD}_1 \lor \dots \lor \textsf{BAD}_m.$$

By a union bound, we have

$$\Pr[\textsf{BAD}] \le \sum_i \Pr[\textsf{BAD}_i],$$

which is still very small.  Moreover, if $\textsf{BAD}$ does not happen, then we have

$$B(m) \le \sum_i 10 \sigma_i = 10 \sqrt{n}/2 \sum_i {1 \over \sqrt{2}^i} \le 10 \sqrt{n}/2 \times 3.5 = O(\sqrt{n}).$$

In other words, there is a constant $c$ such that $B(m) \le c \times \sqrt{n}$ with overwhelmingly high probability.

(I've shamelessly handwaved and glossed over details all over the place to present the intuition in a clean way, but even correcting for them isn't going to change the bottom-line answer.)