2

I have never seen such an equation:

$$T(n) = T\left(\frac n2 + \sqrt n\right) + n$$

Is it possible to solve?

If yes, how? I mean is there any general method for it or something?
thanks.

Ali Caglayan
  • 5,726
Sida
  • 681
  • 2
    First what I'd try were to define it for $n^2$ so $T(n^2)=T((n^2+2n +1)/2-1/2)+n^2 = T(((n+1)^2-1)/2)+n^2$ and then try to find out a pattern... However, that is not yet an analytical solution... – Gottfried Helms Oct 11 '13 at 10:14
  • You want an asymptotic expression in terms of big-$\Theta$, right? –  Oct 11 '13 at 11:06
  • 1
    Look at $T(4)$ - we get the impossible equation $T(4)= T(4)+4$. So the definition of your recurrence needs some refinement if it shall not involve $T(4) = \infty$ ... – Gottfried Helms Oct 11 '13 at 13:51

2 Answers2

1

For every $c$, the property that $T(n)\leqslant2n+7\sqrt{n}+c$ is hereditary for every $n\geqslant10^4$. Likewise, for every $c$, the property that $T(n)\geqslant2n-c$ is hereditary for every $n$. One can choose $c$ large enough so that both properties are satisfied for every $n\leqslant10^4$, then $2n-c\leqslant T(n)\leqslant2n+7\sqrt{n}+c$ for every $n$. In particular, $T(n)\sim2n$ when $n\to\infty$.

Did
  • 279,727
0

Try $T(n) = 2n + an^{1/2}+ b(n)$ where $b(n)$ is small compared with $n^{1/2}$
Treat $\sqrt{n}$ as small compared with $n$ or $n/2$. Solve for $a$, knowing you can correct for the square-root by changing $b(n)$
$$2n+a\sqrt{n}+b(n)=n+2\sqrt{n}+a\sqrt{n/2+\sqrt{n}}+b(n/2+\sqrt{n})+n$$ Cancel $2n$ from one side and $n+n$ from the other. To leading order, what remains is $$a\sqrt{n}=2\sqrt{n}+a\sqrt{n/2}+...$$ Solve for $a$, then go to the next-largest terms. (Hint: I think they are $O(\log n)$)

Empy2
  • 50,853