Please follow instructions for each

1.) Order the functions in increasing order of growth rate (from slowest growing to fastest). You need to explain your answers in detail to get full credit for this question. When two adjacent functions have the same growth rate, note that by underlining them. You can assume that the base of the log is 2:

10n, 2n2, lg(n5), lg lg n, n3+n2+nlgn+210, 2lgn, n, 105, n14, n lg n

2.) Use the formal definitions of , O, and to prove the following:

(a) f(n) =n2+ 2n + 5(n2)

(b) f(n) =ni=1((i1)i)(n3)

(For (b), you will need a formula for the sum of the squares of the first n positive integers: http://www.9math.com/book/sum-squares-first-n-natural-numbers)

3.) Give () running times for each of the following functions, as a function of n. Provideanexplanationfor your answers. Note that when an inner loop variable depends on the outer loop variable, you need to do a summation to get the .

(a)

public static int func1(int n) { int res = 1; for (int i = 1 ; i <= n; i++) { for (int j = 2*n; j >= 1; j--) { res *= j*j; } for (int k = 1; k <= n/2; k++) { res *= k; } for (int m = 1; m <= n*n; m++) { res *= m; } } return res; }

(b)

//(Note that i is multipliedby 2 after each iteration, and that i goes to 4n, not to n.) public static int func2(int n){ int sum = 0; for (int i = 1; i <=4n; i *= 2) sum++; return sum; }

(c)

//Note that in the j loop, j goes to n^3, and that the number of iterators of the inner most loop depends on j. public static int func3(int n){ int sum = 0; for ( int i = 0 ; i < n ; i++) for (int j = 0 ; j < n*n*n; j++) for( int k = 0; k < j ; k++) sum++; return sum; }