1
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – ashkan khademian Oct 30 at 12:11
  • $\begingroup$ I'm sorry, you'll have to work it out on your own. $\endgroup$ – Yuval Filmus Oct 30 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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