What is the asymptotic bound on the summation?

Question

$n + (1/2)n + (1/2)^2n + (1/2)^3n + ... + (1/2)^{log_2n}n$
Doesn't get me anywhere if I apply sum of a GP. Kind of stuck at this step.

Answer 1

Lets start by writing your expression as a sum, as suggested in the comments by Antonio Vargas:

$$n\sum_{k=0}^{\log _2n}\left(\frac{1}{2}\right)^2$$

Now lets consider the sum without including the outer $n$. Lets also take the limit where $\log _2n$ goes to infinity:

$$\lim_{\log _2n\rightarrow\infty}\sum_{k=0}^{\log _2n}\left(\frac{1}{2}\right)^2=2$$

The above sum is something you might have seen before, and as we know it will be equal to two. Now we have an upper bound of the original expression, i.e.:

$$n\sum_{k=0}^{\log _2n}\left(\frac{1}{2}\right)^2 \le n\lim_{\log _2n\rightarrow\infty}\sum_{k=0}^{\log _2n}\left(\frac{1}{2}\right)^2=2n$$