Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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). $$
