Solve recurrence by repeated substitution [closed]

I am solving a recurrence using repeated substitution method and I am almost done but it seems to me that I need some additional work to finish correctly. I am including an image of my work because typing would be very time-consuming. I will appreciate your feedback. I can see that the problem says that $n = 2^k$ so $k = log_{2}n$ so I can replace every $k$ by $log_{2}n$

closed as unclear what you're asking by adrianN, Evil, David Richerby, Rick Decker, JuhoOct 24 '16 at 18:31

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• for what value of k will n/2^k become 1? Once you find that value of k you need to substitute it in your final expression and compute the value of the summation. Do you get what you are missing? You can then verify your answer by using master's theorem. – Shubham Singh rawat Oct 19 '16 at 3:38
• What exactly is your problem? – adrianN Oct 19 '16 at 7:47
• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Oct 19 '16 at 7:59
• I added new content to the end of the post. Now, my main issue is: What do I do with the summation? I guess that maybe it represents a kind of series that can be replaced by another expression but I just cannot find it. Can you provide some guidance? – JORGE Oct 19 '16 at 14:53
• The necessary formula is in every formulary, e.g. the TCS Cheat Sheet. (You have an unbound variable $k$ there, that's no good.) – Raphael Oct 19 '16 at 14:56

This is the guess & proof method as explained over at our reference question. You have a guess, now prove it correct! The canonical choice would be an inductive proof.

Question:

$T(n) = 4T(\frac{n} {2})+n ,\hspace{0.5cm} if \hspace{0.5cm}n \geq 2$

$\hspace{1.0cm} = 1 ,\hspace{2.2cm} if \hspace{0.5cm}n = 1$

Solution by substitution method:

Generalized form:

$T(n) = 4^kT(\frac{n} {2^k})+n\sum_{n=1}^{k-1}2^i$

Until here you are good, but after this we can further simplify as below:

$\sum_{n=1}^{k-1}2^i$ is a finite geometric progression(GP), thus we use the formula:

$S_n=\frac{a_1(1-r^n)} {1-r} \hspace{0.5cm} when \hspace{0.5cm} r\neq1$

$S_n$ = sum of GP with n terms

$a_1$ = the first term

r = common ratio

n = number of terms

$T(n) = 4^kT(\frac{n} {2^k})+n(2^{k-1}-1)$

put $\frac{n} {2^k}= 1$ ie., $k=\log_2 n$

$T(n) = 1 ,\hspace{2.2cm} if \hspace{0.5cm}n = 1$

$T(n) = 4^{\log_2 n}T(1)+n(\frac{n} {2}-1)$

$T(n) = n^{\log_2 4}+n(\frac{n} {2}-1)$

$T(n) = n^2+\frac{n^2} {2}-n$

Thus, $T(n)=O(n^2)$

• There is so little explanation here I can't tell if this is supposed to be an answer or a transcript of the question. – Raphael Oct 19 '16 at 8:00
• @Raphael what more explanation should I add to this? I have clearly given the solution step by step. – Alwyn Mathew Oct 19 '16 at 8:06
• You do some calculations; the OP has some as well. What are you saying? Did they make a mistake? If so, which? (Plus, you are missing an actual proof as well.) – Raphael Oct 19 '16 at 14:55