1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Hint : Solving $T(n) = 4T(n/2) + n^2$ is same as solving the recurrence you have written. $\endgroup$ – user35837 Apr 7 '17 at 13:36
  • $\begingroup$ Firstly thank you. Secondly, can you explain why is same? $\endgroup$ – Software_t Apr 7 '17 at 13:40
  • $\begingroup$ You can't just ask all questions on your exercise sheet here. $\endgroup$ – Yuval Filmus Apr 7 '17 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_t Apr 7 '17 at 13:56
4
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ Thank you!! In addition, can you give motivation for how to know how to define ${"The- S(n)"}$ ? $\endgroup$ – Software_t Apr 7 '17 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$ – Yuval Filmus Apr 7 '17 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.