# What kind of series / recursion is this?

I'm trying to find the explicit solution / sum of first n elements for the following sequence:

d(2) = 2
d(n) = d(n/2) + n*log2(n)


Can you help me to find out what kind of recursion is this and how can I find the explicit solution and the sum of the first n elements?

I've calculated the first few elements, and it goes like this:

2 + 8 + 24 + 64 + ....


(I've arrived here by trying to calculate the asymptotic running time of the bitonic sorting algorithm on a ring-connected parallel architecture, and this is the last part but I'm stuck with this equation)

-
Since you are trying to find the asymptotic running time, you don't actually need to find the exact/explicit solution, do you? You only need the asymptotic bounds (big-Oh or $\theta$). –  Paresh Nov 27 '12 at 11:15
Yes, you're right! But I don't know if I can apply the big-O rules earlier, or just in the last step. I'd guess that for the recursion I cannot apply the big-O rules, since it'd strongly modify the result. –  zsero Nov 27 '12 at 11:18
Well then you can find the asymptotic bounds directly too, without explicitly solving the recurrence (of course, solving the recurrence is also a correct way). Have a look at this for a good explanation. –  Paresh Nov 27 '12 at 11:25
Just a clarification: By directly, I do not mean without working on it. That is, you cannot say it will be $O(n \log n)$. –  Paresh Nov 27 '12 at 11:31
You are right! I can apply the Master Theorem, and from it it's clear that e = 0, thus T(n) = Th(n^k). I guess that here n*log2(n) works kind of like an n^k. So I believe that the solution is Th(n lg n). –  zsero Nov 27 '12 at 11:51

Since the recurrence is only defined when $n$ is a power of 2, we'll let $n=2^k$ for an integer $k\ge 1$. For ease of writing, we'll denote $\log_2 x\text{ by }\lg x$ so your recurrence may be written as $$d(2^k)=\begin{cases} 2 & \text{if }k=1 \\ d(2^{k-1})+k\:2^k & \text{if }k>1 \end{cases}$$ Now we can repeatedly apply this definition to the terms in brackets: \begin{align} d(2^k) &= [d(2^{k-1})]+k\:2^k \\ &= [d(2^{k-2})+(k-1)2^{k-1}] + k\:2^k =[d(2^{k-2})]+(k-1)2^{k-1} + k\:2^k\\ &= [d(2^{k-3})]+(k-2)2^{k-2}+(k-1)2^{k-1} + k\:2^k\\ &= [d(2^{k-4})]+(k-3)2^{k-3}+(k-2)2^{k-2}+(k-1)2^{k-1} + k\:2^k \end{align} and eventually wind up with $$d(2^k)=(1)2^1+(2)2^2+(3)2^3+\cdots+(k-2)2^{k-2}+(k-1)2^{k-1} + k\:2^k$$ There's a closed form for this (see the notes below), but if you happen not to know it, we can still get an upper bound by slightly rewriting is as $$d(2^k)=(k-(k-1))2^1+(k-(k-1))2^2+\cdots+(k-1)2^{k-1} + k\:2^k$$ and then separating positive and negative terms: \begin{align} d(2^k)&=[k\:2^1+k\:2^2+\cdots+k\:2^k]-[(k-1)2^1+(k-2)2^2+\cdots + (1)2^{k-1}]\\ &\le k\:2^1+k\:2^2+\cdots+k\:2^k \\ &=2k(1+2+4+\cdots 2^{k-1})\\ &=2k(2^k-1) \end{align} now using the fact that $n=2^k$ (and hence $k=\lg n)$ we've shown that $$d(n)\le (2\lg n)(n-1)$$ and we finally have our (expected) asymptotic upper bound $$d(n)=O(n\lg n)$$
• In your last comment you said that $n\lg n$ works "kind of like" an $n^k$. This is intuitively right, but strictly speaking I suspect that your version of the Master Theorem doesn't apply to terms that aren't polynomials.
• I mentioned that there is a closed form for the sum. It follows from the fact that $$x+2x^2+3x^3+\cdots+kx^k=\frac{x}{(x-1)^2}(kx^{k+1}-(k+1)x^k+1)$$ which you can get from the sum of the geometric series $1+x+x^2+\cdots + x^k$ by differentiating. Thus we have the exact solution $d(n)=2n(\lg n-1)+2$ which gives us the stronger asymptotic estimate $d(n)=\Theta(n\lg n)$.