Friday, 24 August 2018

logarithms - 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.
log2(n)k=1nlog2(k22)k2
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 k1log2(k22)k2 converges. Let S denote its sum. Then
log2(n)k=1nlog2(k22)k2=nS(nloglognlogn)xn,
where xn+1.



Edit In fact (see comment below), the OP is interested in Tn=nSi(x) for i=log2(n) and x=12, where, for every i and x,
Si(x)=ik=1(k1)xk=i1k=0kxk+1=x2Ui(x),Ui(x)=i1k=0xk.
The function xUi(x) is the sum of a geometric series, hence, for every x1,
Ui(x)=1xi1x,Ui(x)=1(1x)2(1+ixixiixi1).
Using x=12, this yields
Tn=n(1(i+1)2i).
Since i=log2(n), one gets
$$
n-2(\log_2(n)+1)$$
hence Tn=nΘ(log2(n)). The sequence of general term (Tnn)/log2(n) has the interval [2,1] as limit set.



No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...