Big-O: Why is the time complexity of these loops O(N)?
Look at how many steps the inner loop is taking. It's $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$. However the geometric series tells us:

$$\sum_{k=0}^{\lceil\log n\rceil +c}\frac{n}{2^k} &lt; n\sum_{k=0}^\infty \frac{1}{2^k} = 2n$$