2
$\begingroup$

I have the equation $T(n) = 4T(n/2) + n + log(n)$ for $n\ge2$.

I am considering the case where $n=2^k$

I have come to the conclusion that $T(n)$ follows the following formula:

$\begin{align*}T(n) = [n+\log(n)] & + 4[(n/2)+\log(n/2)] + 4^2[(n/2^2) + \log(n/2^2)] + \ldots \\ &+ 4^{k-1}[(n/2^{k-1}) + \log(n/2^{k-1}] + 4^k[T(0)]\end{align*}$

Based on the formula that for $n\ge b$: $\begin{align*}T(n) = aT(n/b) + f(n)\end{align*}$

$T(n)$ goes to

$\begin{align*}T(n) = f(n) + a\cdot f(n/b) + \ldots + a^i\cdot f(n/b^i) + \ldots + a^{k-1}\cdot f(n/b^{k-1}) + a^k\cdot T(0)\end{align*}$

However, I don't know how to reduce this function. I need determine what the rate of growth, i.e. the order of the function is, in terms of $n$. This is problem 13 in the pdf here.

That pdf also contains the formulas I've used to get thus far.

  • 0
    Updated question with more information.2012-05-11

1 Answers 1

1

Assuming $\log$ means logarithm to base 2, you are already pretty close to a solution; you just need to apply some basic summation formulas:

$\sum_{i=0}^{k-1} x^i = \frac{1-x^k}{1-x}, \sum_{i=0}^{k-1} i x^i = \frac{x-kx^k-(k-1)x^{k+1}}{(1-x)^2}.$

Then $T(n) = \sum_{i=0}^{k-1} 4^i(2^{-i}n + \log(2^{-i}n)) + 4^k T(0) = \sum_{i=0}^{k-1} 2^i + \log(n) \sum_{i=0}^{k-1} 4^i - \sum_{i=0}^{k-1} i 4^i + 4^kT(0).$ Calculating each sum seperately, we get $\sum_{i=0}^{k-1} 2^i = 2^k-1 = n-1$, $\sum_{i=0}^{k-1} 4^i = \frac{4^k-1}{4-1} = \frac{(2^k+1)(2^k-1)}{3} = \frac{(n+1)(n-1)}{3} $, $\sum_{i=0}^{k-1} i4^i = \frac{4-k4^k-(k-1)4^{k+1}}{(1-4)^2}=\frac{4-4^k(4+3k)}{9} = \frac{4-n^2(4+3 \log n)}{9}$. The answer is just putting these together.