3
$\begingroup$

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$
$T(1)=1$

The value of $T(m^2)$ for m ≥ 1 is?

Clearly you cannot apply master theorem because it is not of the form $T(n)=aT(\frac{n}{b})+f(n)$

So I tried Back Substitution:
$T(n)=T(n-1)+\lfloor\sqrt{n}\rfloor$
$T(n-1)=T(n-2)+\lfloor\sqrt{n-1}\rfloor$
therefore,
$T(n)=T(n-2)+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(n-3)+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(n-(n-1))+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(1)+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(1)+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$

I'm stuck up here and the answer is given as -

$T(m^2)=\frac{m}{6}(4m^2 - 3m + 5)$

how to solve and reach the answer?

$\endgroup$

2 Answers 2

2
$\begingroup$

Your problem is that you're ignoring the floors. Make sure that you know what $\lfloor x \rfloor$ means.

It is not hard to check that $$ T(n) = \sum_{k=1}^n \lfloor \sqrt{k} \rfloor. $$ Therefore $$ \begin{align*} T(m^2-1) &= \sum_{k=1}^{m^2-1} \lfloor \sqrt{k} \rfloor \\ &= \sum_{r=1}^{m-1} \sum_{\ell=r^2}^{(r+1)^2-1} \lfloor \sqrt{\ell} \rfloor \\ &= \sum_{r=1}^{m-1} \sum_{\ell=r^2}^{(r+1)^2-1} r \\ &= \sum_{r=1}^{m-1} [(r+1)^2-r^2] r \\ &= \sum_{r=1}^{m-1} (2r+1)r \\ &= \sum_{r=1}^{m-1} 4\binom{r}{2} + 3\binom{r}{1} \\ &= 4\binom{m}{3} + 3\binom{m}{2}. \end{align*} $$ Therefore $$ \begin{align*} T(m^2) &= 4\binom{m}{3} + 3\binom{m}{2} + m \\ &= \frac{4m(m-1)(m-2)}{6} + \frac{3m(m-1)}{2} + m \\ &= \frac{(4m^3-12m^2+8m) + (9m^2-9m) + (6m)}{6} \\ &= \frac{4m^3-3m^2+5m}{6}. \end{align*} $$

$\endgroup$
2
  • 1
    $\begingroup$ @Yuval_Filmus:Why did you choose the upper limit of the outer summation to be $m-1$ instead of anything else? $\endgroup$ Dec 21, 2014 at 3:13
  • $\begingroup$ understood finally! $\endgroup$ Dec 21, 2014 at 10:45
3
$\begingroup$

For a slightly different way to look at his problem, consider your original equation, $$ T(n) = T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor+\dotsb+\lfloor\sqrt n\rfloor $$ Now the key here is to group the terms with the same values of $\lfloor\sqrt k\rfloor$: $$\begin{align} T(n) &= (T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor)\\ &+(\lfloor\sqrt4\rfloor+\lfloor\sqrt5\rfloor+\lfloor\sqrt6\rfloor+\lfloor\sqrt7\rfloor+\lfloor\sqrt8\rfloor)\\ &+(\lfloor\sqrt9\rfloor+\lfloor\sqrt{10}\rfloor+\lfloor\sqrt{11}\rfloor+\lfloor\sqrt{12}\rfloor+\lfloor\sqrt{13}\rfloor+\lfloor\sqrt{14}\rfloor+\lfloor\sqrt{15}\rfloor)\\ &+\dotsc \end{align}$$ and observe that each summand will have $2k+1$ terms, since the difference $(k+1)^2-k^2 = 2k+1$: $$ T(n) = (1\cdot3)+(2\cdot5)+(3\cdot 7)+(4\cdot 9)+\dotsb $$ so we'll have, with $n=m^2$ $$\begin{align} T(m^2) &= (1\cdot3)+(2\cdot5)+\dotsb+\left(\left\lfloor\sqrt{(m-1)^2}\right\rfloor+\dotsb+\left\lfloor\sqrt{m^2-1}\right\rfloor\right)+\left\lfloor\sqrt{m^2}\right\rfloor\\ &=\sum_{k=1}^{m-1}k(2k+1)+m =\sum_{k=1}^{m-1}(2k^2+k)+m\\ &=2\sum_{k=1}^{m-1}k^2+\sum_{k=1}^{m-1}k+m\\ &=2\frac{(m-1)(m)(2(m-1)+1)}{6}+\frac{(m-1)(m)}{2}+m\\ &=\frac{m}{6}(4m^2-3m+5) \end{align}$$ as required.

$\endgroup$

Your Answer

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

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