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