2. a. Design a non-recursive algorithm for computing an (discussed in the class). What is the basic operation? How many times is the algorithms basic operation executed?

b. Using an = a*an-1 (discussed in the class) to design a recursive algorithm for computing an . What is the basic operation? Set up and solve a recurrence relation for the number of times that algorithm's basic operation is executed.

c. Using an = a*(a(n-1)/2) 2 (n is odd integer) and an = (an/2) 2 (n is even integer) (discussed in the class) to design a recursive algorithm for computing an . What is the basic operation? Set up and solve a recurrence relation for the number of times that algorithm's basic operation is executed.