What kind of series / recursion is this?

Question

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)

Answer 1

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) $$

---

Some additional notes

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