• Graph 1: contains all curves with n as the x-axis and f(n) as the y-axis
• Graph 2: contains all curves with log(n) as the x-axis and log(f(n)) as the y-axis.

2. Count the exact number of primitive operations, as a function of n, in the following piece of pseudo-code:

Algorithm SumFactorial(n)
Input: integer n>=1
Output: 1! + 2! + 3! + ... + n!
x <- 0
for i <- 1 to n do

y <- 1
for j <- 1 to i do

y <- y * j

x <- x + y

return x

3. Give the pseudo-code to perform binary search using recursion. Let the input be x and an array A of size n. The algorithm returns either the index i such that A[i]=x, or -1 if x does not exist in A.

• Count the exact number of primitive operations in the algorithm you designed.
• Give the asymptotic running time of the algorithm in either big-Oh, big-Theta, or big-Omega.

4. Goodrich & Tamassia (G&T) R-1.15

5. G&T R-1.19

6. G&T R-1.22

7. G&T C-1.10

8. G&T C-1.27

1. G&T R-6.2

2. G&T R-6.4

3. G&T R-6.10

4. G&T C-6.2

5. G&T C-6.3

6. G&T R-7.1

7. G&T C-7.2