Sign up ×

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.

share|cite|improve this question
I didn't know how to format it where you see the red. I want the entire (k-1) to be raised in superscript or exponent. Anyone know how to do that? –  canton May 11 '12 at 11:59
Try "4^{k-1}". Also, for the log function, use "\log". –  Will Orrick May 11 '12 at 12:04
Thank you @WillOrrick –  canton May 11 '12 at 12:12
Updated question with more information. –  canton May 11 '12 at 12:21

1 Answer 1

up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


