Preceding the proposed recurrence solution 1.9 we have the very clear table and I understand that we can group by powers of two, that $J(n)$ is always 1 at the start of the group, and it increases by 2 within a group.
I'm having trouble understanding what is meant by "what's left" in this sentence
So if we write $n$ in the form of $n = 2^m + l$, where $2^m$ is the largest power of 2 not exceeding $n$ and where $l$ is what's left, the solution to our recurrence seems to be …
Does the author mean what's left of the power-of-two group? Or what's left of the people involved in the elimination circle?
Best Answer
$\ell$ is $n-2^m$. That is, the difference between $n$ and the largest power of $2$ not exceeding $n$.
(I think "what's left" is the author's way of informally referring to the portion of $n$ that is not 'contained' in some power of $2$. )