0
$\begingroup$

I need to solve the following recurrence relation:

$$ \begin{align*} T(1) &= c_1\\ T(2) &= c_2\\ T(n) &= T(\lfloor\frac{n+2}{2}\rfloor) + c_3, \end{align*} $$

where $c_1$, $c_2$ and $c_3$ are constants. The thing is, I really don't know how to battle the $T(\lfloor\frac{n+2}{2}\rfloor)$ part. I don't need an explicit answer, I just need to know wherever it will be logarithmic (i.e. can be upper bounded by $\mathcal{O}(\log{}n)$). I'll be glad for any ideas how to prove/disprove it.

$\endgroup$
1
  • $\begingroup$ does this happen to be about Fibonacci numbers and matrix multiplication? $\endgroup$ – 5201314 Mar 9 at 13:01
1
$\begingroup$

For simplicity assume $n=2^k,k\in \mathbb \{3,4,\cdots \}$. Then $$\left\lfloor\frac{n+2}{2}\right\rfloor=\left\lfloor\frac{n}{2}+\frac12\right\rfloor=\left\lfloor\frac{2^k}{2}+\frac12\right\rfloor=\left\lfloor2^{k-1}+\frac12\right\rfloor=\lfloor2^{k-1}\rfloor$$ So \begin{align*} T(n)&=T(2^{k-1})+c_3=T(2^{k-2})+2c_3=T(2^{k-3})+3c_3+\cdots =T(2)+kc_3\\ &= c_2+kc_3=c_2+c_3\log n=O(\log n) \end{align*}

$\endgroup$

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.