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 ∑k≥1log2(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)=i∑k=1(k−1)xk=i−1∑k=0kxk+1=x2U′i(x),Ui(x)=i−1∑k=0xk.
The function x↦Ui(x) is the sum of a geometric series, hence, for every x≠1,
Ui(x)=1−xi1−x,U′i(x)=1(1−x)2(1+ixi−xi−ixi−1).
Using x=12, this yields
Tn=n(1−(i+1)2−i).
Since i=⌊log2(n)⌋, one gets
$$
n-2(\log_2(n)+1)
hence Tn=n−Θ(log2(n)). The sequence of general term (Tn−n)/log2(n) has the interval [−2,−1] as limit set.
No comments:
Post a Comment