# 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}$

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$$ $$

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

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?

• I did not get you Commented Jul 9, 2020 at 21:00
• I jumped the step, substituted $c_i$ with $i$ or $1$ and then changed the variables to $j$ Commented Jul 9, 2020 at 21:06

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

• $\text{lg}=\log_2$? Commented Jul 9, 2020 at 21:10
• @UmbQbify-Key20-: Yes; it’s a standard abbreviation. (And you can get it with \lg.) Commented Jul 9, 2020 at 21:11
• Specifically for base 2 logarithm? Thanks! Commented Jul 9, 2020 at 21:14
• @UmbQbify-Key20-: Yes, specifically for the binary log. Commented Jul 9, 2020 at 21:15
• @AbhishekGhosh: Oops! You’re absolutely right, and I need to change the answer slightly. Thanks! (Because I can’t see the question when I’m typing an answer, I sometimes lose track of details.) Commented Jul 10, 2020 at 16:01