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 )

Exercises A.2-5

Filed under: A.2 — yuhanlyu @ 2:29 pm

Because \int^n_0 1/x dx when x = 0 is undefined value.

Exercises A.2-4

Filed under: A.2 — yuhanlyu @ 2:24 pm

\int^{n+1}_1 x^3 dx = (n+1)^4/4 - 1/4
\int^n_0 (x-1)^3 dx = n^4/4
\sum^n_{k=1} k^3 = \Theta(n^4)

Exercises A.2-3

Filed under: A.2 — yuhanlyu @ 2:19 pm

\sum^n_{k=1} 1/k
\geq \sum^{\lceil \lg n \rceil - 1}_{i=0} \sum^{2^i-1}_{j=0} 1/(2^i+j)
\geq \sum^{\lceil \lg n \rceil - 1}_{i=0} \sum^{2^i-1}_{j=0} 1/2^i
\geq \sum^{\lceil \lg n \rceil - 1}_{i=0} 1
= \Omega(\lg n)

Exercises A.2-2

Filed under: A.2 — yuhanlyu @ 7:54 am

\sum^{\lfloor \lg n \rfloor}_{k=1} \lceil n/2^k \rceil is obviously \Omega(n)
\sum^{\lfloor \lg n \rfloor}_{k=1} \lceil n/2^k \rceil
\leq \sum^{\lfloor \lg n \rfloor}_{k=1} n/2^k + 1
\leq n + \lg n
=O(n) Then
\sum^{\lfloor \lg n \rfloor}_{k=1} \lceil n/2^k \rceil = \Theta(n)

Exercises A.2-1

Filed under: A.2 — yuhanlyu @ 7:50 am

\sum^n_{k=1} 1/k^2
\leq 1+ \sum^n_{k=2} 1/k(k-1)
= 1 + \sum^n_{k=2} 1/(k-1) - 1/k
= 1 + 1 - 1/n
< 2

Indeed, \sum^{\infty}_{k=1} 1/k^2 = {\pi}^2/6

Exercises A.1-8

Filed under: A.1 — yuhanlyu @ 2:08 am

\prod^n_{k=2} (1-1/k^2)
= \prod^n_{k=2} (k^2 - 1)/k^2
= \prod^n_{k=2} (k+1)(k-1)/k^2
= (n+1)/2n

Exercises A.1-7

Filed under: A.1 — yuhanlyu @ 2:02 am

\prod^n_{k=1} 2*4^k
= 2^k \prod^n_{k=1} 4^k
= 2^k * 4^{k(k+1)/2}
= 2^k * 2^{k(k+1)}
= 2^{k(k+2)}

Exercises A.1-6

Filed under: A.1 — yuhanlyu @ 1:57 am

Solution Wanted

Exercises A.1-5

Filed under: A.1 — yuhanlyu @ 1:51 am

Let f(x) = \sum^{\infty}_{k=0} x^k = 1/(1-x)
Let g(x) = f'(x) = \sum^{\infty}_{k=0} kx^{k-1} = 1/(1-x)^2
g(x) = \sum^{\infty}_{k=0} kx^{k-1}
= \sum^{\infty}_{k=1} (k+1)x^k
\sum^{\infty}_{k=1} (2k+1)x^{2k}
= (g(x) + g(-x))/2 when |x| < 1

Older Posts »

Blog at WordPress.com.