0
$\begingroup$

Let $n\in\mathbb{Z}^+$ and $T_n = 1\sqrt{1} + 2\sqrt{2} +\cdots+ n\sqrt{n}$.

Finding $\mathcal{O}(T_n)$, $\mathcal{\Omega}(T_n)$ and $\mathcal{\Theta}(T_n)$

  • 0
    thanks to anon. I have a solution same with yours. And $\Theta(T_n) = \sqrt{n^5}$2011-11-01

1 Answers 1

1

$T_n = \Theta(n^{5/2})$

$T_n = 1 \sqrt{1} + 2 \sqrt{2} + \cdots + n \sqrt{n} < n \times n \sqrt{n} = n^{5/2}$

Also $\forall k \in \{0,1,2,\ldots,n\}$, $ \frac{k \sqrt{k} + (n-k) \sqrt{n-k}}{2} > \frac{n}{2} \sqrt{\frac{n}{2}}$

This gives that $T_n = 1 \sqrt{1} + 2 \sqrt{2} + \cdots + n \sqrt{n} > n \times \frac{n}{2} \sqrt{\frac{n}{2}} = \frac{n^{5/2}}{2^{3/2}}$

In general, as anon has in his comment, $\displaystyle \sum_{k=1}^{n} k^s - \frac{n^{s+1}}{s+1} = \mathcal{\Theta}(n^{s})$

  • 0
    This is my solution $T_n = \sum_{i = 1}^{n} k^{3/2} \geq \sum_{i = n/2}^{n} \left(\frac{n}{2}\right)^{3/2} = \left(n - \lceil{\frac{n}{2}}\rceil + 1\right)\cdot\left(\frac{n}{2} \right)^{3/2} \geq \alpha\cdot\sqrt{n^5}$2011-11-01