How can I calculate or at least approximate the sum? As a part of a complexity analysis of the algorithm, I have to calculate the following sum:
$$n^{1/2} + n^{3/4} + n^{7/8} + ...$$ where in total I have $k$ elements to sum: $$\sum_{i=1}^{k}n^{(2^i-1)/2^i}$$
Here $n$ is a fixed number.
After trying to derive the explicit formula, I gave up and tried to approximate it with the integral, which I was not able to calculate. Is there a way to get a formula or at least find the order of growth of this function when k-> $\infty $?
P.S. apart from the obvious thing that the sum is less than $k \cdot n$

Using the inequality $e^{-x} \ge 1-x$, we have:
$\displaystyle\sum_{i = 1}^{k}n^{-\tfrac{1}{2^i}}$ $= \displaystyle\sum_{i = 1}^{k}e^{-\tfrac{1}{2^i}\ln n}$ $\ge \displaystyle\sum_{i = 1}^{k}\left(1-\dfrac{1}{2^i}\ln n\right)$ $= k-\left(1-\dfrac{1}{2^k}\right)\ln n$. 
Thus, $kn-\left(1-\dfrac{1}{2^k}\right)n\ln n \le \displaystyle\sum_{i = 1}^{k}n^{1-\tfrac{1}{2^i}} \le kn$. 
So for fixed $n$ and large $k$, the sum is slightly less than $kn$.
