0
$\begingroup$

I try to find the time complexity of following recurrence relation: $$T(n) = 3T(n-2) + O(n)$$ After subtitution,I get: $$T(n)=3^{\frac{n}{2}}T(0)+\sum_{i=0}^{\frac{n}{2}-1}3^iO(n-2i)$$

I wonder if the ans is $O(3^{\frac{n}{2}})$ or $O(3^{\frac{n}{2}} n)$, can someone give a help to determine the ans and give a proof about it.

$\endgroup$
1
  • $\begingroup$ Note that big-O stays correct if the right side is unnecessarily large. 3^(n/2) * n is unnecessarily large. $\endgroup$
    – gnasher729
    Oct 24, 2023 at 13:35

1 Answer 1

0
$\begingroup$

Recurrence relations do not have time complexities, algorithms do.

That said, assuming $T(1)=O(1)$ and $T(2)=O(1)$, both $T(n)=O(3^{n/2})$ and $T(n)=O(3^{n/2} n)$ are true. Indeed: $$ T(n) = 3T(n-2)+O(n) =3^i T(n-2i) + \sum_{j=0}^{i-1} 3^j O(n-2j) \quad \text{for }i<n/2, $$ choosing $i=\lfloor n/2 \rfloor - 1 $: $$ \begin{align} T(n) &= 3^{\lfloor n/2 \rfloor - 1} \cdot O(1) + \sum_{j=0}^{\lfloor n/2 \rfloor - 2} 3^j O(n-2j) = O\left( \sum_{j=0}^{\lfloor n/2 \rfloor - 2} 3^j (n-2j) \right) \\ &= O\left(3^{n/2} \sum_{j=0}^{\infty} \frac{1}{2^i} \right) = O(3^{n/2}). \end{align} $$

Where we used the fact that each term of the summation increases by at least a factor of $2$ compared to the previous one. Indeed: $$ \frac{3^{j+1} (n-2j-2)}{3^j (n-2j)} = 3\left(1-\frac{2}{n-2j}\right) \ge 3\left(1-\frac{2}{n- 2(\lfloor n/2 \rfloor - 3)}\right) \ge 2. $$

The above shows that $T(n) = O(3^{n/2})$, which also implies $T(n)=O(3^{n/2} n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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