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 need to find the closed form solution to the following recurrence -:

$ T(n) = 8*T(n/2) + 0.25*n^2$ with $T(1) = 1$ and $n=2^j$ and this is what I have tried so far but just can't seem to get a pattern out for this recurrence. Letting 0.25 to behave as a variable x, I have,

$T(n) = T(n/2) + n^2*x$

$T(2) = 8 + 2^2 * x $

$T(4) = 8*(8 + 2^2 * x) + 4^2 * x $

$T(8) = 8*(8*(8 + 2^2 * x) + 4^2 * x) + 8^2 * x $

I extracted the highest power of 8 from the above equation for T(8), to check if I can find a pattern but couldn't how can I possibly solve this recurrence?

share|improve this question

4 Answers 4

Each $i$ with $1\le i\le j$ contributes $8^{j-i}(2^i)^2x$ to the value of $T(2^j)$, and we get $8^j$ for the base case. So we must have $$ T(2^j) = 8^j + \sum_{i=1}^j 8^{j-i}(2^i)^2 x = 8^j + \sum_{i=1}^j 4^j 2^{j-i} x = 8^j + 4^jx \sum_{k=0}^{j-1} 2^k = 8^j + 4^j(2^j-1)x$$ or, reinserting $n=2^j$, $$ T(n) = n^3 + n^2(n-1)x $$ when $n$ is a power of 2.

share|improve this answer
    
I understood it fully :) thanks a lot, but btw shouldn't for the base case the contribution be $8^j * x$ ? –  AnkitSablok Sep 25 '13 at 20:14
    
@AnkitSablok: No because the base case is $T(1)=1$, not $T(1)=x$. (Note that $T(1)=T(2^0)$, corresponding to the $i=0$ case that is not in the summation). –  Henning Makholm Sep 25 '13 at 20:15
    
okk so for the base case, the contribution doesn't account for x, thanks for explaining :D I am grateful to you for the time you devoted, going to upvote the answer :) –  AnkitSablok Sep 25 '13 at 20:18

You may be interested to know that the recurrence $$ T(n) = 8\;T(\lfloor n/2 \rfloor) + 1/4 \; n^2 $$ where $T(0) = 0$ and $T(1) = 1/4$ actually has a closed form solution for all $n$ and not just for $n$ a power of two. (We will show how to solve this with $T(1) = 1$ at the end of this post.)

This closed form is obtained by unrolling the recursion according to the binary digits of $n.$ Let those digits be given by $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Then the closed form solution (exact for all $n$) is given by $$ T(n) = \frac{1}{4} \sum_{k=0}^{\lfloor \log_2 n \rfloor} 8^k \left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} d_j 2^{j-k} \right)^2.$$

To get an upper bound consider the case of all one digits, which gives $$ T(n) \le \frac{1}{4} \sum_{k=0}^{\lfloor \log_2 n \rfloor} 8^k \left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} 2^{j-k} \right)^2 = \frac{20}{21} 8^{\lfloor \log_2 n \rfloor} - 4^{\lfloor \log_2 n \rfloor} + \frac{1}{3} 2^{\lfloor \log_2 n \rfloor} - \frac{1}{28}.$$ This bound is attained.

To get a lower bound consider the case of a one digit followed by a string of zeros, giving $$ T(n) \ge \frac{1}{4} \sum_{k=0}^{\lfloor \log_2 n \rfloor} 8^k \left( 2^{\lfloor \log_2 n \rfloor-k} \right)^2 = \frac{1}{2} 8^{\lfloor \log_2 n \rfloor} - \frac{1}{4} 4^{\lfloor \log_2 n \rfloor}.$$ This bound too is attained.

Joining these two it now becomes evident that $$T(n)\in \Theta\left(8^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{3\lfloor \log_2 n \rfloor}\right) = \Theta(n^3).$$

The above calculation has $T(1) = 1/4$ while the query asks for $T(1) = 1$. It is not difficult to see that the answer to the original query can be obtained by taking $$ T(n) + \frac{3}{4} 8^{\lfloor \log_2 n \rfloor}.$$

This gives the following upper and lower bounds $$ \frac{143}{84} 8^{\lfloor \log_2 n \rfloor} - 4^{\lfloor \log_2 n \rfloor} + \frac{1}{3} 2^{\lfloor \log_2 n \rfloor} - \frac{1}{28} \quad\text{and}\quad \frac{5}{4} 8^{\lfloor \log_2 n \rfloor} - \frac{1}{4} 4^{\lfloor \log_2 n \rfloor}.$$ The asymptotic complexity is not affected.

There is more material on this method here.

share|improve this answer

Without converting 0.25 to a variable x, I found that T(n) = $8^{log_2n}(1+\sum_{i=0}^n\frac{1}{8x})$, but whether that's a closed form I don't know

share|improve this answer

[EDIT: it seems the question is restricted to powers of $2$ where the integer and real recurrence are the same. With that restriction the following is a complete solution, but is aimed at the unrestricted problems, for general integer or real values of $n$]

As usual with these algorithm recurrences, the smoothed problem where real-valued $\frac{n}{2}$ is used instead of integer $n$ DIV $2$, has a cleaner solution and tells the asymptotics. There might be a chance of a closed form for the the integer problem if you write everything in binary digits of $n$. For the smoothed problem this one has a nice answer.

Writing $T(n) = n^3 x S(n)$ removes the difficulty with the $8$ and cleans up the $x$ in the last term. $$S(n) = S(n/2) + \frac{1}{n}$$.

Observe that $S_0(n)=\frac{-1}{n}$ is a solution.
The general solution is to add a solution of $f(n)=f(n/2)$ to $S_0$.

Conclusion:

$$T(n) = x(-n^2 + n^3f(n))$$ where $f$ is a function with $f(n)=f(n/2) \quad$ [equivalently, $f(2^x)$ has period $1$]

This means that if in the integer problem you start the recurrence at large enough $n$, prescribing the early values arbitrarily, the asymptotics are $T(n) = Cn^3 + O(n^2)$ with $C$ determined by the early values. In fact $C$ will be a linear function of those values, a simple enough thing in principle, but the coefficients are potentially quite complicated.

[EDIT: in the restricted problem with powers of $2$,the function $f(n)$ is a constant. To fit $T(1)$ the constant should be selected so that $T(1)=x(-1 + f)$. Then $T(n)=x(n^3 - n^2) + n^3 x (f-1) = x(n^3 - n^2) + T(1)n^3$.]

share|improve this answer

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.