I have to solve the recurrence relation
$$T(n)=\left\{\begin{matrix} 3T\left (\frac{n}{4} \right)+n & , n>1\\ 1 &, n=1 \end{matrix}\right.$$
and prove by induction that the solution I found is right.
I found that the solution of the recurrence relation is $T(n)=O(n)$.
I started proving it like that:
- $n=1: T(1)=1 \leq c \cdot 1 \checkmark \text{ for } c \geq 1$
- We suppose that for any $m$, $2 \leq m <n , n>2$: $T(m) \leq c \cdot m$.
- We want to show that the claim stands for $n$.
But, then I noticed that we do not have a formula for $T \left ( \frac{n}{4} \right)$ when $n<4$ and also when $n \neq 4^k$.
So, do we have to suppose that $n \geq 4$ and $n=4^k$ ?
If so, at which point of the proof, do I have to claim it?
By way of enrichment we solve another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = 3 T(\lfloor n/4 \rfloor) + n.$$
Furthermore let the base four representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_4 n \rfloor} d_k 4^k.$$
Then we can unroll the recurrence to obtain the following exact formula for $n\ge 1$ $$T(n) = \sum_{j=0}^{\lfloor \log_4 n \rfloor} 3^j \sum_{k=j}^{\lfloor \log_4 n \rfloor} d_k 4^{k-j}.$$
Now to get an upper bound consider a string of three digits which yields $$T(n) \le \sum_{j=0}^{\lfloor \log_4 n \rfloor} 3^j \sum_{k=j}^{\lfloor \log_4 n \rfloor} 3 \times 4^{k-j} = 16\times 4^{\lfloor \log_4 n \rfloor} -\frac{27}{2} 3^{\lfloor \log_4 n \rfloor} + \frac{1}{2} .$$
Note that this bound is attained and cannot be improved.
The lower bound is for the case of a one digit followed by a string of zeros and yields $$T(n) \ge \sum_{j=0}^{\lfloor \log_4 n \rfloor} 3^j \times 4^{\lfloor \log_4 n \rfloor-j} = 4\times 4^{\lfloor \log_4 n \rfloor} - 3\times 3^{\lfloor \log_4 n \rfloor}.$$
This bound too is attained.
Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$4^{\lfloor \log_4 n \rfloor} \in \Theta\left(4^{\log_4 n}\right) = \Theta(n).$$
These are in agreement with what the Master theorem would produce.
Here is another MSE link where some similar computations are carried out.