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
    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$).2012-11-27
  • 0
    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.2012-11-27
  • 0
    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](http://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf) for a good explanation.2012-11-27
  • 0
    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)$.2012-11-27
  • 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
    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.2012-11-27
  • 0
    @zsero. Ah, I see. I'll edit my answer accordingly.2012-11-27