Bounding Summation

Question

How does the below bounds to logn?

Please explain the steps 1 and 2.

I came to know that they are using the idea of splitting the summations and bounding them.

How the first and second step came?

Comments

Yea I know that. That's why I called it 'unconventional' and 'pending'

---

@kushagra-I got to understand why in the first step, the summation is from 0 to log n,

but then we had multiplied it with another summation of j from 0 to 2ⁱ-1and the term $\frac{1}{2^{i}+j}$

---

Ayush That is not multiplication that is called double summation. Its computation is similar to computing the nested for loops. In this case the for loops are

sum = 0

for  i=0 to log n 

    for  j=0 to 2ⁱ - 1

         sum = sum + (1/ (2ⁱ +j) )

    end for

end for

Try to write the sum I think you will get why they are using log n.

To get u started

for i=0 sum = 1

for i=1 sum = 1 + 1/2 + 1/3

for i=2 sum = 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7

do it like this.