0

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)$

qwerty89
  • 726
  • 1
    Have you had calculus? If so, you might think about $\int_0^n x\sqrt{x} dx$ – Brian M. Scott Nov 01 '11 at 08:07
  • Well, there's $$\sum_{k=1}^n,k^s=n^{s+1}\sum_{k=1}^\infty \frac{1}{n}(k/n)^s\sim n^{s+1}\int_0^1x^sdx=\frac{n^{s+1}}{s+1}.$$ You're question is pretty vague though, as there's always more than one type of $O,\Omega,\Theta$ applicable for a given function. – anon Nov 01 '11 at 08:08
  • thanks to anon. I have a solution same with yours. And $\Theta(T_n) = \sqrt{n^5}$ – qwerty89 Nov 01 '11 at 08:13

1 Answers1

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})$$

  • 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}$$

     – qwerty89 Nov 01 '11 at 08:41