Using the master theorem to find an upper bound for $T$, where $T(x) \leq 4 T(\left \lfloor{\frac{x}{2}} \right \rfloor) + x$

Question

Let $x \in \mathbb{N}$. We have the relation: $T(x) \leq 4 T(\left \lfloor{\frac{x}{2}} \right \rfloor) + x$. I am trying to find an upper bound for $T$.

if $x$ is a power of $2$ i.e. $x = 2^n$. I have found that: $T(2^m) \le 4^{m}(T(1)+1-\frac1{2^m})$ for some $m\geq n$. I am having troubles generalising this for $x \in \mathbb{N}$

Answer 1

What you found suggests $T(2^m)=O(4^m)$.

Let $2^m\leq n\leq2^{m+1}$, so $$T(2^m)\leq T(n)\leq T(2^{m+1})=O(4^{m+1})=O(4\times4^m)=O(4^m)$$