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.

  • $\begingroup$ Are you satisfied with the solution $T(n)=n$? $\endgroup$
    – zkutch
    Oct 30, 2020 at 1:14

1 Answer 1


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). $$

  • $\begingroup$ 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. $\endgroup$ Oct 30, 2020 at 12:11
  • 1
    $\begingroup$ I'm sorry, you'll have to work it out on your own. $\endgroup$ Oct 30, 2020 at 12:18
  • $\begingroup$ A great answer. $\endgroup$
    – John L.
    Oct 27, 2021 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.