Question:
Find the best possible order for $ T(n) $, for sufficiently large values of $ n $.
$ T(n) = 2T\left(\frac{n}{2}+\sqrt{n}\right)+T\left(\frac{n}{2}\right)+1 $
My try:
Here is my attempt at finding the solution using induction to prove $T(n) \le cn^{\log_{2 - \varepsilon}(3)} + b$:
$ \begin{align*} \varepsilon & > 0 \\\\ T(n) & \leq 3T \left( \frac{n}{2} + \sqrt{n} \right) + 1 \\\\ & \leq 3T \left( \frac{n}{2 - \varepsilon} \right) + 1 \quad \text{(For n )} \\\\ T(n) & \leq 3c \left( \frac{n}{2 - \varepsilon} \right)^{\log_2(3)} + 3b + 1 \\\\ & = \frac{3cn^{\log_{2 - \varepsilon}(3)}}{(2 - \varepsilon)^{\log_{2 - \varepsilon}(3)}} + 3b + 1 \\\\ T(n) & \leq cn^{\log_2(3)} + 3b + 1 \leq cn^{\log_2(3)} + b \quad \text{if } b < -\frac{1}{2} \\\\ \varepsilon & > 0 \Rightarrow T(n) \in O \left( n^{\log_{2 - \varepsilon}(3)} \right) \end{align*} $
What I can't find:
Provide a proof that setting $\varepsilon = 0$ is permissible.
$ T(n) = 2T\left(\frac{n}{2}+\sqrt{n}\right)+T\left(\frac{n}{2}\right)+1 \in O \left( n^{\log_{2}(3)} \right)$