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.
Answer
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.
No comments:
Post a Comment