Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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