What is the complexity of $T(n) =3T((n-2)/2) + n^2$?

Question

I have to find the complexity of a recursive function that has this form: $$T(n) =\left\{\begin{aligned} &3T((n-2)/2) + k_2n^2&&\text{ when }n > 1\\ &k_1 &&\text{ when } n = 1 \end{aligned}\right.$$ I have met $ T(n) = a*T(n/b) + n $, which resolves with Master Method, and $ T(n) = T(n-1) + n $ which resolves with iterative, but this is mixed, and I can't find a solution to it.

I have discovered that if I try it the iterative way starting from $T(n-2)$ and continuing with $ 3^k T( n/(2^k) )$, I end up with $ T(n-2) = 3^k*3T( n / (2^k2) ) + \sum_{i=0}^k( 3^i ( n /2^k - 2))$ but this leads nowhere. How can I find this solution?

note that: $T(n+2)=3T\bigg(\cfrac{n}{2} \bigg) +(n+2)^2=3T\bigg(\cfrac{n}{2} \bigg) +\Theta(n^2)$ — Rick Sanchez C-666, Nov 22 '20 at 17:31

score 1 · Answer 1 · answered Nov 22 '20 at 17:44

1

$$\bullet \quad \text{Note that: } T(n+2)=3T\bigg(\cfrac{n}{2} \bigg) +(n+2)^2=3T\bigg(\cfrac{n}{2} \bigg) +\Theta(n^2)$$ $$\text{Master Theorem } \implies T(n+2)=\Theta (n^2 )\iff T(n)=\Theta \big( (n-2)^2\big)=\Theta (n^2)$$ $$\implies \bbox[5px,border:1.5px solid red] {\color{black}{ T(n)=\Theta(n^2)}}$$

(note: $\log_2(3)<\log_2(4)=2$)

answered Nov 22 '20 at 17:44

Rick Sanchez C-666

1,010

as far as i know , Master Theorem works for T(n). Does it apply for T(n+c) as well? – Robert Maracine Nov 22 '20 at 18:01
it can be, only if we a-priori know that the time complexity is something like $\Theta(a^n \cdot n^k \cdot \log^p (n))$ and not something like $\Theta(n!)$ . – Rick Sanchez C-666 Nov 23 '20 at 15:29

score 1 · Answer 2 · answered Nov 22 '20 at 17:49

It'll need at least an $n^2$ behaviour, to match the last term on the right. Try $T(n)\sim cn^2$ so, for large $n$, $3T(n/2-1)\sim 3cn^2/4$. Equating $n^2$ coefficients, $c=3c^2/4+1$ i.e. $c=4$. On the other hand, a nonzero $n^p$ coeffiient can't be matched for $p>3$. So $T(n)\sim 4n^2\in\Theta(n^2)$.

What is the complexity of $T(n) =3T((n-2)/2) + n^2$?

2 Answers2