Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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

1 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)$.
share|improve this answer
    
Thanks for this detailed answer! It really did answer all my questions both in math and with algorithm-theory. Sorry, I wasn't clear with the series in the question, what I've calculated is the following elements of the sum, not the actual values in the recursion. I've update it with +, to make it easier to understand. –  zsero Nov 27 '12 at 20:32
    
@zsero. Ah, I see. I'll edit my answer accordingly. –  Rick Decker Nov 27 '12 at 20:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.