# How to find ${O(T(n)=4T(\frac{n-2}{2}) +n^2)}$

In given:
$${T(n)=4T(\frac{n-2}{2}) +n^2 }$$ How can i find ${O(T(n))}$ ?

• Hint : Solving $T(n) = 4T(n/2) + n^2$ is same as solving the recurrence you have written. – user35837 Apr 7 '17 at 13:36
• Firstly thank you. Secondly, can you explain why is same? – Software_t Apr 7 '17 at 13:40
• You can't just ask all questions on your exercise sheet here. – Yuval Filmus Apr 7 '17 at 13:53
Let $S(n) = T(4n-2)$. Then $$S(n) = T(4n-2) = 4T\left(\frac{4n-4}{2}\right) + \Theta(n^2) = 4T(2n-2) + \Theta(n^2) = 4S(n/2) + \Theta(n^2).$$ The master theorem tells us that $S(n) = \Theta(n^2\log n)$, and so $T(n) = \Theta(n^2\log n)$.
More generally, the statement of the Akra–Bazzi theorem (specifically, the $h_i$ functions) makes it clear that the small perturbation in this recurrence ($\frac{n-2}{2}$ instead of $\frac{n}{2}$) doesn't change the asymptotics of the solution. From this theorem you can derive the solution directly without guessing the substitution $S(n) = T(4n-2)$.
• Thank you!! In addition, can you give motivation for how to know how to define ${"The- S(n)"}$ ? – Software_t Apr 7 '17 at 14:15
• You look for a function $f(n)$ that satisfies $\frac{f(n)-2}{2} = f(n/2)$. Given a value for $f(1)$, you can calculate $f(n)$ for all powers of 2, and if you're lucky, the function has a simple expression in terms of $n$. – Yuval Filmus Apr 7 '17 at 14:29