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.

  • 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 comple$x$ity 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) 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.

  • 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