1
$\begingroup$

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)

  • 0
    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).2012-11-27

1 Answers 1

2

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)$.
  • 0
    @zsero. Ah, I see. I'll edit my answer accordingly.2012-11-27