1
$\begingroup$

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.

  • 0
    I am curious. What algorithm produces such a strange summation? :-)2011-03-30
  • 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.2011-03-31

1 Answers 1

3

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)

  • 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.2011-03-30
  • 0
    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?2011-03-31
  • 0
    @Michael: Yes. Since the terms involved are positive the sum upto $\log n$ is less than the sum upto $\infty$ which is constant.2011-03-31
  • 0
    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?2011-04-03