1
$\begingroup$

So I've been working on this recurrence equation and I'm stumped at the end. $T(n) = T(n/2) + n\log(n);\: T(1) = 1;\: n = 2^k$ and $\log $ is base $2$.

$T(2^k) = T(2^{k-1}) + 2^k \log(2^k)$

$T(2^k) = T(2^{k-1}) + (2^k) k$

$T(2^{k-1}) = T(2^{k-2}) + 2^{k-1} \log (2^{k-1})$

$T(2) = T(1) + 2^{1}\cdot(1)$

$T(1) = 1$

$T(2^k) = 1 + \displaystyle \sum_{i=0}^{ k} (2^i) (k-i)$

I'm not sure if I did everything correct, but I'm confused about tackling the summation.

$\endgroup$
  • $\begingroup$ I think you mean the terms in the summation to be $i\cdot 2^i$, not $(k-i)2^i$ $\endgroup$ – Peter Huxford Sep 24 '14 at 4:18
  • $\begingroup$ But if it's starting at 0, wouldn't that eliminate some terms? $\endgroup$ – recurrenceprobs Sep 24 '14 at 4:32
  • $\begingroup$ You don't need to start it at 0 actually. The sum should be $1\times2^1 + 2\times2^2 + \cdots + k\times2^k$, which is equal to $\sum_{i=1}^k i\cdot2^i$ $\endgroup$ – Peter Huxford Sep 24 '14 at 4:36
1
$\begingroup$

To assure you about the summation I separated the terms of the final sums in a likely better patternizable form:
$ \qquad \qquad \displaystyle \small \begin{array} {} T(1)&=&1 &=&1&=&3-1\cdot2\\ T(2^1)&=&1+1 \cdot2^1 &=&3&=&3+0\cdot4 \\ T(2^2)&=&1+1 \cdot2^1+2 \cdot2^2 &=&11&=&3+1\cdot8\\ T(2^3)&=&1+1 \cdot2^1+2 \cdot2^2 +3 \cdot2^3 &=& 35&=&3+2\cdot16\\ T(2^4)&=&1+ ...+4 \cdot2^4 &=& 99&=&3+3\cdot32\\ T(2^5)&=&1+ ...+5 \cdot2^5 &=& 259&=&3+4\cdot64\\ \end{array}$

The pattern $1x+2x^2+3x^3+4x^4+...$ (where here $x=2$) can also be represented by a generating function of the style $ a/ (1-x)^2$ and this can be adapted to match the sum-expressions above as truncation of the occuring series to make the final formula below rigorous. This is the generating function:

$ \qquad \qquad \displaystyle G(m,x)= 1+{x \cdot (1-x^{m+1})-(m+1) \cdot x^{m+1} \cdot (1-x) \over (1-x)^2}$
From this, evaluated at $x=2$ we get the expression for $T(n$)

$ \displaystyle \qquad \qquad T(n)=G(\log_2(n),2) \\ \qquad \qquad \qquad = 1+2 \cdot { (1-2^m)+m \cdot 2^m \over (-1)^2} \qquad \qquad \qquad \text{ ( where } m=\log_2(n) \text{ )}\\ \qquad \qquad \qquad = 1+2 \cdot (1-n+\log_2(n) \cdot n) $

and finally

$ \qquad \qquad \displaystyle { T(n) = 3 + (\log_2(n)-1)\cdot2 \cdot n }$

(which is the result as was previously given in the answer of pjhuxford)

$\endgroup$
0
$\begingroup$

Your working is mostly fine, except the final summation.

So for any $i\geq1$, as you showed: \begin{align*} T(2^i)&=T(2^{i-1})+i\cdot2^i \\ \implies T(2^i)-T(2^{i-1})&=i\cdot2^i \\ \implies \sum_{i=1}^k (T(2^i)-T(2^{i-1})) &= \sum_{i=1}^k i\cdot2^i \end{align*}

The left side telescopes, giving $T(2^k)-T(1)=T(2^k)-1$, so we have

$$T(2^k)=1+\sum_{i=1}^k i\cdot2^i$$

Now, to evaluate this summation, I'm not too sure of a direct way of the top of my head. If you happen to know it in advance, its not too bad to prove by induction.

I claim that $$\sum_{i=1}^k i\cdot2^i=(k-1)2^{k+1}+2$$

You can check it holds when $k=1$. Suppose it holds when $k=n$. Then:

\begin{align*} \sum_{i=1}^{n+1}i\cdot2^i&=(n+1)2^{n+1}+\sum_{i=1}^n i\cdot2^i \\ &=(n+1)2^{n+1}+(n-1)2^{n+1}+2 \\ &= n2^{n+2}+2 \\ &= ((n+1)-1)2^{(n+1)+1}+2 \end{align*}

So the formula also holds when $k=n+1$. This proves the clame, and consequently

$$T(2^k)=1+(k-1)2^{k+1}+2=(k-1)2^{k+1}+3$$

If you wanted to rewrite this in terms of $n$, just use the fact that $2^k=n$ and $\log n=k$ (using $\log$ to base 2). Then, provided $n$ is a power of 2, the recurrence becomes:

$$T(n)=2n(\log(n)-1)+3$$

$\endgroup$
  • $\begingroup$ That makes sense! One more question, I ultimately have to substitute n back in (since i replace it for 2^k) to get the recurrence equation, correct? $\endgroup$ – recurrenceprobs Sep 24 '14 at 5:17
  • $\begingroup$ I don't think that was very clear from the way you wrote the question. In the original recurrence, must $n$ be a power of 2? In any case, if $n=2^k$, then using $\log$ to base 2, $k=\log n$, so the recurrence becomes: $T(n)=2(\log(n)-1)n+3$, however I have only shown this to be the case when $n$ is a power of 2. $\endgroup$ – Peter Huxford Sep 24 '14 at 5:22
  • $\begingroup$ Yes we can assume n is a power of 2. Sorry for the confusion. I'm still getting the hang of this stuff $\endgroup$ – recurrenceprobs Sep 24 '14 at 5:27
  • $\begingroup$ Don't worry about it :) $\endgroup$ – Peter Huxford Sep 24 '14 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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