Recurrence Relation when n is a fraction?

Question

If I have the following: $$T(n) = T(n/2) + 3$$

Where $n > 1$ and $T(1) = 2$, how do can I solve for odd $n$ values (e.g. $T(3) = T(3/2) + 3$) ?

Answer 1

Suppose, $2^k\le n< 2^{k+1}$. Then, $\frac{n}{2^k}=1+e,0\le e<1$, where, $k=\log_2{n}$. $$\begin{align}T(n)& =T(n/2)+3\\ &=T(n/4)+3+3=T(n/4)+2\cdot 3\\ &=T(n/8)+3\cdot3=T(n/2^3)+3\cdot 3\\ &\vdots\\ &=T(n/2^k)+k\cdot 3=T(1+e)+3\log_2{n}\\&\le c\cdot T(1)+3\log_2{n}=2c+3\log_2{n}\\&=\mathcal{O}(\log_2{n})\end{align}$$

where $c$ is a constant.

Note: Usually, as you have used the tag discrete-math, this type of recurrence relations come up in computing complexity of an algorithm, where length of input $n$ is always an integer.

Answer 2

You should suppose $n = 2^k$. Now you can solve it easily. Hence, $T(n) = 3(\log(n)-1) + 2 = 3\log(n) + 1$.

Answer 3

You have to write it as $T(n) = T(\lfloor n/2 \rfloor) + 3 $.

This allows you to write the cases for even and odd $n$ as $T(2n)=T(n)+3 $ and $T(2n+1)=T(n)+3 $.