Problem A « Exercise Lover

March 10, 2007

Problems A-1

Filed under: Problem A — yuhanlyu @ 2:42 pm

a. Let $f(x) = \sum^n_(k=1) k^r$ is obviously $O(n^{r+1})$
$f(x) \geq \sum^n_{k=n/2} k^r$
$\geq \sum^n_{k=n/2} (n/2)^r$
$= \Omega(n^{r+1})$
$f(x) = \Theta(n^{r+1})$

b. Let $f(x) = \sum^n_{k=1} \lg^sk$ is obviously $O(n\lg^sn)$
$f(x) \geq \sum^n_{k=n/2} \lg^sk$
$\geq \sum^{n}_{k=n/2} \lg^s (n/2)$
$= \Omega( n\lg^sn )$
$f(x) = \Theta( n\lg^sn)$

c. Let $f(x) = \sum^n_{k=1} k^r \lg^sk$ is obviously $O(n^{r+1} \lg^sn)$
$f(x) \geq \sum^n_{k=n/2} k^r\lg^sk$
$\geq \sum^n_{k=n/2} (n/2)^r \lg^s(n/2)$
$= \Omega( n^{r+1} \lg^sn )$
$f(x) = \Theta( n^{r+1} \lg^sn )$