Can anyone give me some hint on solving $T(n) = T(\frac{n}{2} + \sqrt{n}) + n$, with any method, master method, substitution....I have came up with this : $T(n) = T(\frac{(\sqrt{n} + 1)^{2} - 1}{2}) + n$ and then substituting $n = 2^{m}$ but things gets really messy !any idea?
Solving a recurrence
algorithm analysis
Here sufficient base cases are not provided. If the recurrence is rewritten as follows$T(n)=T( \lfloor n/2+\sqrt{n} \rfloor)+n$, then, from an initial value $n>4$, in a finite number of steps, one reachs the value $n=4$. In these conditions, we can use the Akra-Bazzi theorem, cf.https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_methodHere $g(x)=x,a_1=1,b_1=1/2,h(x)=\sqrt{x}+O(1)$. Thus $p=0$ and $T(x)=\Theta(x)$.Remark: as Yuval wrote, we can also use a recurrence. For instance, we try to prove that $T(n)\leq cn$. The condition to show is $c(n/2+\sqrt{n})+n\leq cn$, that is $c>2$ and $n\geq \dfrac{4c^2}{(c-2)^2}$. We choose $c\geq 20$ and the considered inequality is true for $n\geq 5$. We must begin the recurrence, that is $T(4)\leq 4c$. Finally $c=\sup \{20,T(4)/4\}$.