# How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

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.