Computer Science 3650
Summer 2000
Exercise 1

1. (Exercise 2.2-4, page 37) Show that lg(n!) = THETA(n lg(n)). (THETA is the big-theta). You will need to use Stirling's approximation, found on page 35.

         n! = sqrt(2 pi n) (n/e)n (1 + THETA(1/n))
     

   where e = 2.718... is the base of the natural logarithms.

2. (exercise 2-2, page 38) Indicate, for each pair of expressions (A,B) in the table below, whether A is O, o, OMEGA, omega, or THETA of B. Assume that k >= 1, e > 0 and c > 1 are constants. Your answer should be in the form of the table with "yes" or "no" written in each box.

   A	B	O	o	OMEGA	omega	THETA
   lgk n	ne
   nk	cn
   sqrt(n)	nsin n
   2n	2n/2
   nlg m	mlg n
   lg(n!)	lg(nn

3. (exercise 3.1-1, page 45) Find a simple formula for Sumⁿ_{k = 1}(2k-1). (Sum is the big Sigma.)

4. (exercise 3-1, page Use bounding to give asymptotically tight bounds on the following summations. That is, express each as THETA of some function. Assume that r > 0 and s > 0 are constants.

   1. Sumⁿ_{k = 1} k^r

   2. Sumⁿ_{k = 1} lg^s k

   3. Sumⁿ_{k = 1} k^rlg^sk