patternMinor
Need help about solving a recurrence relation
Viewed 0 times
solvingneedhelprecurrenceaboutrelation
Problem
I have a recurrence relation which is like the following:
$T(n) = 2T(\frac{n}{2}) + \log_{2}n$
I am using recursion tree method to solve this. And at the end, i came up with the following equation:
$T(n)=(2\log_{2}n)(n-1)-(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$ where $k=\log_{2}n$
I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum $(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$. How can I find a big theta notation for $T(n)$?
$T(n) = 2T(\frac{n}{2}) + \log_{2}n$
I am using recursion tree method to solve this. And at the end, i came up with the following equation:
$T(n)=(2\log_{2}n)(n-1)-(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$ where $k=\log_{2}n$
I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum $(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$. How can I find a big theta notation for $T(n)$?
Solution
For $\sum_{0 \le r \le k} r \cdot 2^r$, start with:
$$
\frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} z^r
$$
As this is a polynomial, the following mangling doesn't need any justification:
$$
z \frac{d}{dz} \frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} r z^r
$$
Doing the operations indicated:
$$
\sum_{0 \le r \le k} r z^r = \frac{z^k (k z^2 - (k + 1) z) + z}{(1 - z)^2}
$$
Finally:
$$
\sum_{0 \le r \le k} r 2^r = (2 k - 2) 2^k + 2 = \Theta(k 2^k) = \Theta(n \log n)
$$
$$
\frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} z^r
$$
As this is a polynomial, the following mangling doesn't need any justification:
$$
z \frac{d}{dz} \frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} r z^r
$$
Doing the operations indicated:
$$
\sum_{0 \le r \le k} r z^r = \frac{z^k (k z^2 - (k + 1) z) + z}{(1 - z)^2}
$$
Finally:
$$
\sum_{0 \le r \le k} r 2^r = (2 k - 2) 2^k + 2 = \Theta(k 2^k) = \Theta(n \log n)
$$
Context
StackExchange Computer Science Q#10346, answer score: 2
Revisions (0)
No revisions yet.