How to solve the recursive complexity?

Question

I have such recursive complexity $T(n) = T(n-2) + log(n)$. The problem is that I cant use a recursion tree or the master theorem. The only way, which I know, is to guess and then proof the answer.

Any ideas?

Answer 1

Opening the recursion $$ T(n)=T(n-2)+\log(n)=T(n-4)+\log(n-2)+\log(n)=...=T(0)+\log(2)+...+\log(n-2)+\log(n) $$

Thus $$ T(n)=c+\sum_{i=1}^{n}\log(2i)=c+\log(\Pi_{i=1}^{n}2i) $$

Now note that
$$ \log(\Pi_{i=1}^{n}2i)=\log(2^{n}\Pi_{i=1}^{n}i)=\log(2^{n}n!)=\log(2^{n})+\log(n!)\underbrace{=}_{\text{Using Stirling' approximation}}2\log(n)+\theta(n\log n)=\theta(n\log n) $$

For more details see Stirling's approximation