College of Computer & Information Science Spring 2005 Northeastern University Handout 3 CSU690: Algorithms and Data 10 January 2005

Recitation 1

1. Prove by induction on n ≥ 0 that

∑_{i=1}^{n} i^{3} = \frac{n^{2}(n + 1)^{2}}{4} .

2. Exercise 2.2-2, page 27.

3. Arrange the following functions in order from the slowest growing function to the fastest growing function. Briefly justify your answers. (Hint: It may help to plot the functions and obtain an estimate of their relative growth rates. It may also help to express each function as a power of 2 and then compare.)

(lg n)^{20} n^{1/4} 2^{n/100}