HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Need help about solving a recurrence relation

Submitted by: @import:stackexchange-cs··
0
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)$?

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)
$$

Context

StackExchange Computer Science Q#10346, answer score: 2

Revisions (0)

No revisions yet.