# Convert a sum contain a log function to geometric series

I'm trying to calculate the complexity of an algorithm. I've managed to boil down the cost of the algorithm to the following sum.
$$\sum_{k = 1}^{\log_{2}(n)} \frac{n\log_{2}(\frac{k^{2}}{2})}{k^{2}}$$ where $n$ is the size of the data set.

I'm struggling to turn the sum into a function that I can use to figure out the big-$O$ of my algorithm. I was initially thinking that if I could convert the sum into a geometric series, then I might have something that I could work with.

-
I am curious. What algorithm produces such a strange summation? :-) –  Aryabhata Mar 30 '11 at 21:50
If you have a map/reduce type of algorithm where the reduction doesn't return a single value, but a list of values (e.g. similar to a merge sort), then the cost of the reduction dominates. In most functional languages lists are immutable so the cost of combining lists is either O(n) or O(log n) depending on the implementation. I managed to show that if the list concatenation was O(n) based on the size of 1 half of the reduction then the total reduction complexity came to O(n log n), but stumbled with the other one. I'm writing a blog post, I'll post a link when it's done. –  Michael Barker Mar 31 '11 at 6:03

The series $\displaystyle\sum_{k\ge1}\frac{\log_{2}(\frac{k^{2}}{2})}{k^{2}}$ converges. Let $S$ denote its sum. Then $$\sum_{k = 1}^{\log_{2}(n)} \frac{n\log_{2}(\frac{k^{2}}{2})}{k^{2}}=nS-\left(n\frac{\log\log n}{\log n}\right)x_n,$$ where $x_n\to+1$.
Edit In fact (see comment below), the OP is interested in $T_n=nS_i(x)$ for $i=\lfloor \log_2(n)\rfloor$ and $x=\frac12$, where, for every $i$ and $x$, $$S_i(x)=\sum_{k=1}^i(k-1)x^k=\sum_{k=0}^{i-1}kx^{k+1}=x^2U'_i(x),\quad U_i(x)=\sum_{k=0}^{i-1}x^{k}.$$ The function $x\mapsto U_i(x)$ is the sum of a geometric series, hence, for every $x\ne1$, $$U_i(x)=\frac{1-x^i}{1-x},\qquad U'_i(x)=\frac1{(1-x)^2}(1+ix^i-x^i-ix^{i-1}).$$ Using $x=\frac12$, this yields $$T_n=n(1-(i+1)2^{-i}).$$ Since $i=\lfloor \log_2(n)\rfloor$, one gets $$n-2(\log_2(n)+1)<T_n<n-\log_2(n),$$ hence $T_n=n-\Theta(\log_2(n))$. The sequence of general term $(T_n-n)/\log_2(n)$ has the interval $[-2,-1]$ as limit set.
Or more simply there are constants $c_1, c_2$ such that the sum $T(n)$ in question satisfies $c_1 n \le T(n) \le c_2n$ and so $T(n) = \theta(n)$. I only mention this because OP views this from a Computer Science perspective. –  Aryabhata Mar 30 '11 at 21:59
@Michael: Yes. Since the terms involved are positive the sum upto $\log n$ is less than the sum upto $\infty$ which is constant. –  Aryabhata Mar 31 '11 at 5:50
I made a mistake and the actual sum is $\displaystyle\sum_{k = 1}^{\log_{2}(n)} \frac{n\log_{2}(\frac{2^k}{2})}{2^k}$. I can see the the $S$ portion would still converge, but is the remaining term affected? –  Michael Barker Apr 3 '11 at 11:15