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
$\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$
  • 1
    $\begingroup$ @Yuval_Filmus:Why did you choose the upper limit of the outer summation to be $m-1$ instead of anything else? $\endgroup$ – Siddharth Thevaril Dec 21 '14 at 3:13
  • $\begingroup$ understood finally! $\endgroup$ – Siddharth Thevaril Dec 21 '14 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, privacy policy and cookie policy

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