The provided recurrence relation is as follows:
$$ T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2 $$
The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately, the Master's Theorem and Akra-Bazzi methods do not apply directly to this recurrence. Drawing a recursion tree would be quite challenging due to the square root term. Also I know about induction to prove the bounds, but I need a good guess that I'm not able to find it.
Any helps are appreciated!
It’s asymptotically the same as the simple recurrence $$T'(n)=8T'(n/4)+n^2,$$ which solves to $T'(n)\sim2n^2$ by any of the common methods (where as usual, I write $f(n)\sim g(n)$ for $\lim_{n\to\infty}f(n)/g(n)=1$).
On the one hand, $T'(n)\sim2n^2$ provides an upper bound on $T$. If you want to only estimate the recurrence up to $\Theta$, you are done: $n^2\le T(n)\le T'(n)=O(n^2)$ gives $$T(n)=\Theta(n^2).$$ For a more precise estimate, let us unwind the recurrence: $$\begin{align*} T(n)&=n_0^2+8n_1^2+8^2n_2^2+\cdots,\\ n_0&=n,\\ n_{i+1}&=(n_i-\sqrt{n_i})/4. \end{align*}$$ You can prove by induction on $i$ that for any constant $i\ge0$, $$n_i\sim4^{-i}n.$$ It follows that for any constant $k$, the sum of the first $k$ terms of $T(n)$ is $${}\sim(2-2^{1-k})n^2.$$ Thus, for any constant $\epsilon>0$, $T(n)\ge(2-\epsilon)n^2$ for sufficiently large $n$ (depending on $\epsilon$), that is, $$T(n)\sim2n^2.$$ More precisely, one can show that both $T(n)$ and $T'(n)$ are $2n^2+O(n^{3/2})$ (where the hidden constant depends on the initial conditions).
$(n - \sqrt n) / 4$ is slightly smaller than n/4, for example >= $n \cdot (3/16)$ if n >= 16. So you get a lower limit if you take $8T(n \cdot (3/16)) + n^2$
If n >= 64, then $n - \sqrt n >= n \cdot (7/8)$, and the larger n is, the closer that factor is to 1. You take $8T(n \cdot (7/32)) + n^2$ as a lower bound if n >= 64, and so on as n grows. Combine the results, and you get the same results as for $8T(n / 4) + n^2$.
This is big-O. For small n, $n - \sqrt n$ is substantially smaller than n, so there will be a very small constant factor. You can define T(0) = c, and use $T(\lfloor (n - \sqrt n) / 4 \rfloor) + n^2$ for n >= 1 and calculate the first 1000 values to see this.
