How to find a closed form solution to a recurrence of the following form?

Question

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?

Answer 1

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.

Answer 2

[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$.]

Answer 3

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

Answer 4

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.