# Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$

in one of my college assignments i came up with the following recursive function which I'm ask to solve: $$T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$$

I could not use master method on it and it is not an LHR either. I assume this must have something to do with recursion tree but i cant figure the relation if so.

• Are you satisfied with the solution $T(n)=n$? – zkutch Oct 30 '20 at 1:14

When $$n$$ is large, $$T(n-\sqrt{n})$$ is much larger than $$T(\sqrt{n})$$. Therefore, roughly speaking, $$T(n) \approx T(n-\sqrt{n}) + \Theta(n).$$ Now let us imagine extending $$T$$ to all inputs, and suppose that it was differentiable. Then $$T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$$, and consequently $$T'(n) \approx \Theta(\sqrt{n}) \Longrightarrow T(n) = \Theta(n^{3/2}).$$
Armed with this guess, let us now attempt to show that it indeed describes the order of growth of your recursion. On the one hand, unrolling $$T(n) \geq \Theta(n) + T(n - \sqrt{n})$$, we get $$T(n) \geq \Theta(n + (n-\sqrt{n}) + \cdots + (n-\lfloor \sqrt{n}/2 \rfloor \sqrt{n})).$$ Here there are $$\Omega(\sqrt{n})$$ summands, each of which is at least $$n/2$$, and so $$T(n) = \Omega(n^{3/2})$$.
In the other direction, let us assume that $$\Theta(n) \leq Cn$$, and let us try to prove inductively that $$T(n) \leq Kn^{3/2}$$. For the inductive step to go through, we would need $$K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2}.$$ The mean value theorem shows that for some $$\theta_n \in [0,1]$$, $$n^{3/2} - (n - \sqrt{n})^{3/2} = \sqrt{n} \cdot \frac{3}{2} \sqrt{n-\theta_n \sqrt{n}} \geq \sqrt{n} \cdot \frac{3}{2} \sqrt{n - \sqrt{n}},$$ which is at least $$n$$ for $$n \geq 4$$. Therefore for $$n \geq 4$$, we have $$K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2} - Kn + Kn^{3/4} + Cn.$$ For $$n \geq 16$$, we have $$n^{3/4} = n \cdot n^{-1/4} \leq 16^{-1/4} n = n/2$$, and so $$K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2} + (C-K/2)n,$$ which is at most $$Kn^{3/2}$$ if $$K \geq 2C$$.
More generally, similar arguments should show that if $$k(n) = o(n)$$ then the recurrence $$T(n) = T(k(n)) + T(n-k(n)) + \Theta(n)$$ should have the solution $$T(n) = \Theta\left(\int \frac{n\,dn}{k(n)}\right).$$
• Thanks for the answer. I just don't get the induction part where you resulted in $T(n) < Kn^{3/2}$. I'll be so grateful if you give me extra explain. – ashkan khademian Oct 30 '20 at 12:11