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$

Proceeding naively,
$\begin{array}\\
\sum_{i=1}^{k}n^{(2^i-1)/2^i}
&=\sum_{i=1}^{k}n^{1-1/2^i}\\
&=\sum_{i=1}^{k}nn^{-1/2^i}\\
&=n\sum_{i=1}^{k}e^{-\ln n/2^i}\\
&\approx n\sum_{i=1}^{k}(1-\ln n/2^i+(\ln n/2^i)^2/2)\\
&=n\sum_{i=1}^{k}1-n\ln n\sum_{i=1}^{k}1/2^i+\frac12 n\ln^2 n\sum_{i=1}^{k}1/4^i\\
&=nk-n\ln n(1-1/2^k)+\frac12 n\ln^2 n\frac{1/4-1/4^{k+1}}{1-1/4}\\
&\approx nk-n\ln n+\frac16 n\ln^2 n\\
\end{array}
$
Since the series for
$e^{-x}$ is,
I believe,
enveloping,
the sum should be between
the partial sums of this.
However,
it looks to me that
the sums should be split into
two regions:
$2^i < \ln n$
and
$2^i \ge \ln n$
because the asymptotics
are different for these.
However,
it is late and 
I will leave it like this.
