Finding the summation of $c_i$ for $c_i=\begin{cases}i &\quad\text{if $i-1$ is exact power of $2$ }\\1&\quad\text{otherwise.}\\ \end{cases}$

Question

While reading the text Introduction to Algorithms by Cormen et. al. I came across a few mathematical step which I felt like proving in a more detailed manner, as I could not get steps of the mathematics which they did in short.

Below is the excerpt from the text.

$$c_i = \begin{cases} i &\quad\text{if $i-1$ is an exact power of $2$ }\\ 1&\quad\text{otherwise.}\\ \end{cases}$$

So,

$$\sum_{i=1}^{n}c_i\leq n+\sum_{j=0}^{\lfloor lg(n) \rfloor}2^j\tag 1$$ $$<n+2n=3n$$

---

The following is my attempt to understand the step $(1)$

$$\sum_{i=1}^{n}c_i=\sum_{\text{$i-1$ is a power of 2}}c_i +\sum_{\text{$i-1$ is not a power of 2}}c_i $$

$$=\sum_{\text{$j$ is a power of 2}}(j+1) +\sum_{\text{$j$ is not a power of 2}}(1) ,\quad\quad\text{where $j=i-1$}$$

$$=\sum_{\text{$j$ is a power of 2}}(j) +\sum_{\forall j}(1) = \left (\sum_{\text{$j$ is a power of 2}}j\right )+n \tag 2$$

$$\text{where $0\leq j \leq n-1$}$$

for the situation in which $j$ is power of $2$ let $2^k$ be the maximum possible value of $j$. So,

$$2^k=n-1 \implies k=\lfloor \log_2(n-1) \rfloor$$

Now we know,

$$n-1<n \implies \log_2(n-1)<\log_2(n) \implies \lfloor\log_2(n-1)\rfloor\leq\lfloor\log_2(n)\rfloor \tag3$$

Let $j=2^t$ , $t=0$ to $k$

So from $(2)$ and $(3)$ we have,

$$\sum_{i=1}^{n}c_i\leq n+\sum_{t=0}^{\lfloor lg(n) \rfloor}2^t \tag 4$$

The step which the authors achieved directly in $(1)$ took me so many steps to understand or derive in $(4)$. Is there a shorter method available or some intuition which the authors used to achieve the result directly?

Answer 1

If $i-1=2^j$, where $i\le n$ then $j=\lg(i-1)<\lg n$. Moreover, $j$ is an integer, so $j\le\lfloor\lg n\rfloor$. Thus, each term of $\sum_{i=1}^nc_i$ is either $1$ or $2^j+1$ for some $j$ such that $0\le j\le\lfloor\lg n\rfloor$. Thus, we automatically get a contribution of $1$ from each of the $n$ terms, for a total of $n$. We get another $2^j$ for the terms with $0\le j\le\lfloor\lg n\rfloor$, which contribute

$$\sum_{j=0}^{\lfloor\lg n\rfloor}2^j=2^{\lfloor\lg n\rfloor+1}-1<2\cdot2^{\lg n}=2n\;.$$

Thus,

$$\sum_{i=1}^nc_i\le n+\sum_{j=0}^{\lfloor\lg n\rfloor}2^j<n+2n=3n\;.$$