How can I solve this piecewise recurrence relation?

137 Views Asked by At

The recurrence relation is \begin{equation} T(n)= \begin{cases} \Theta(1) & \text{if } n=1\\ 2T(n/2)+\Theta(n) & \text{if } n \space is\space even\\ T(n-1)+\Theta(n) & \text{if } n\space is\space odd \space \wedge n\neq 1 \end{cases} \end{equation} Which denotes the total time for a specific algorithm on an input of size $n$.

I am not sure how to deal with the piecewise definition, it seems that $T(n)=\Theta(T_M(n))$ where $T_M(n)=T_M(\lfloor n/2\rfloor)+T_M(\lceil n/2 \rceil)$. Then it would be easy to use the master theorem.

1

There are 1 best solutions below

0
On BEST ANSWER

For any odd $n \ne 1$, $T(n) = T(n-1) + \Theta(n)=2T\left(\frac{n-1}{2}\right) +\Theta(n)+\Theta(n) = 2T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) +\Theta(n)$

Now just use master Theorem or draw recurrence tree