In given:
$${T(n)=4T(\frac{n-2}{2}) +n^2 }$$
How can i find ${O(T(n))}$ ?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Hint : Solving $T(n) = 4T(n/2) + n^2$ is same as solving the recurrence you have written. $\endgroup$– user35837Commented Apr 7, 2017 at 13:36
-
$\begingroup$ Firstly thank you. Secondly, can you explain why is same? $\endgroup$– Software_tCommented Apr 7, 2017 at 13:40
-
$\begingroup$ You can't just ask all questions on your exercise sheet here. $\endgroup$– Yuval FilmusCommented Apr 7, 2017 at 13:53
-
$\begingroup$ I just asked it about this post: cs.stackexchange.com/questions/29230/… it's not related to exercise sheet... $\endgroup$– Software_tCommented Apr 7, 2017 at 13:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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)$.
answered Apr 7, 2017 at 14:06
-
$\begingroup$ Thank you!! In addition, can you give motivation for how to know how to define ${"The- S(n)"}$ ? $\endgroup$ Commented Apr 7, 2017 at 14:15
-
1$\begingroup$ 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$. $\endgroup$ Commented Apr 7, 2017 at 14:29