Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I am curious. What algorithm produces such a strange summation? :-) –  Aryabhata Mar 30 '11 at 21:50
1  
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
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
3  
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
    
Thank you for the prompt response. @Moron Cheers for the analysis. Is it valid to use use the limit as k approaches infinity to show that the function converges? –  Michael Barker Mar 31 '11 at 5:46
    
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.