0
$\begingroup$

Can anyone give me some hint on solving $T(n) = T(\frac{n}{2} + \sqrt{n}) + n$, with any method, master method, substitution.... I have came up with this : $T(n) = T(\frac{(\sqrt{n} + 1)^{2} - 1}{2}) + n$ and then substituting $n = 2^{m}$ but things gets really messy !

any idea?

$\endgroup$
1
$\begingroup$

Here sufficient base cases are not provided. If the recurrence is rewritten as follows $T(n)=T( \lfloor n/2+\sqrt{n} \rfloor)+n$, then, from an initial value $n>4$, in a finite number of steps, one reachs the value $n=4$. In these conditions, we can use the Akra-Bazzi theorem, cf.

https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method

Here $g(x)=x,a_1=1,b_1=1/2,h(x)=\sqrt{x}+O(1)$. Thus $p=0$ and $T(x)=\Theta(x)$.

Remark: as Yuval wrote, we can also use a recurrence. For instance, we try to prove that $T(n)\leq cn$. The condition to show is $c(n/2+\sqrt{n})+n\leq cn$, that is $c>2$ and $n\geq \dfrac{4c^2}{(c-2)^2}$. We choose $c\geq 20$ and the considered inequality is true for $n\geq 5$. We must begin the recurrence, that is $T(4)\leq 4c$. Finally $c=\sup \{20,T(4)/4\}$.

$\endgroup$
3
$\begingroup$

Assuming that the end goal is to get an asymptotic bound on the time or space complexity of the algorithm that this recurrence relation represents, then start with $n = 4k^2$ s.t. $k > 1$ and notice the following:

$T(4k^2) = T(2k^2 + 2k) + 4k^2$

$T(2k^2 + 2k) = T( k^2 + k + \sqrt{ 2k(k + 1) } ) + 2k^2 + 2k$

$T(k^2 + k + \sqrt{ 2k(k + 1) }) = T(\ldots) + k^2 + k + \sqrt{ 2k(k + 1) }$

Substituting backward

$T(4k^2) = 7k^2 + 3k + \sqrt{ 2k^2 +2k } + T(\ldots)$

Substituting the original value of $n$

$T(n) = \frac{7}{4} n + \frac{3}{2} \sqrt{n} + \sqrt{\frac{1}{2}n + \sqrt{n}} + T(...) $

Each successive term is an order smaller than the one prior and as we look at the asymptotic behavior, those smaller terms will vanish and the linear term will dominate, thus $\mathcal{O}(n)$.

$\endgroup$
1
$\begingroup$

Hint: You can prove inductively that $T(n) \leq Cn$ for an appropriate $C$. On the other hand, clearly $T(n) \geq n$.

$\endgroup$
  • $\begingroup$ I followed you hint here it is: $T(n) \le C(\frac{n}{2} + \sqrt{n}) + n$ and we have $T(n) \le n(\frac{C}{2}+1) + \sqrt{n} \le n$ for $C \le -2$, is my argument correct? $\endgroup$ – Hadi Amiri Sep 27 '13 at 17:28
  • $\begingroup$ Try to think what $C \leq -2$ says on the solution. Do you expect $T(n) \leq Cn$ in this case? $\endgroup$ – Yuval Filmus Sep 27 '13 at 17:56
1
$\begingroup$

The function $T$ is not defined over $\mathbb{N}$ because if $n$ is an integer, then $n/2+\sqrt{n}$ is not in general. Perhaps a floor function is missing in the definition. Assume that $T$ is defined on $(0,+\infty)$. Let $t>4$. Then the sequence $u_0=t,u_{k+1}=u_k/2+\sqrt{u_k}$ is decreasing and tends to $4$. Thus $T(t)>4+4+\cdots$ and $T(t)=+\infty$.

$\endgroup$

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.