Can somebody help me bound the following sum in terms of Big-O?
$$\sum_{i=1}^{\lg\lg n} n^{1-\frac{1}{2^i}}$$
I've figured out that it is $O(n \lg\lg n)$ by
$$ \begin{align} \sum_{i=1}^{\lg\lg n} n^{1-\frac{1}{2^i}}&=n\sum_{i=1}^{\lg\lg n} n^{-\frac{1}{2^i}}\\ &\leq n\sum_{i=1}^{\lg\lg n}1\\ &=O(n\lg\lg n) \end{align} $$
but that is too loose.
Is it even possible to get a $O(n)$ bound?
Yes, it is possible. The last term of $\sum_{i=1}^{\lg\lg n}n^{-1/2^i}$ is at most $n^{-1/2^{\lg\lg n}}=1/2$, and for the rest, the $i$-th term is the square of the $(i+1)$-th. Thus, this sum has an upper bound of $\sum_{k=0}^{\infty}2^{-2^k}$, which is finite.