Timeline for To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2014 at 22:42 | comment | added | Yuval Filmus | The extra $7$ is there since $7T(n/2) = 7(7T(n/4) + (n/2)^2)$. | |
| Apr 17, 2014 at 22:41 | comment | added | user16666 | I have a doubt here : when we substitute n/2 in place of n calculating T(n/2) = 7 T(n/4) +(n/2)^2 , and after putting the value of T(n/2) in original equation it should be 7^2T(n/4) + (n/2)^2 + n^2 But in your proof above its: 7^2T(n/2^2)+7(n/2)^2+n^2. I want to know where is this extra 7 coming from (I mean 7(n/2)^2) | |
| Apr 17, 2014 at 22:39 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
added 2 characters in body
|
| Apr 17, 2014 at 17:41 | history | answered | Yuval Filmus | CC BY-SA 3.0 |