Answer to Question #44894 in Programming & Computer Science for Suhaib

Question

1. Describe a recursive algorithm for finding the maximum element in an array A of n elements. What
is the running time of your algorithm?

2. Draw the recursion trace for the execution of reverseArray(data, 0, 4), on the array data = 4, 3, 6, 2, 6.

3. Give an algorithm for finding the second-to-last node in a singly-linked list ub which the last node is
indicated by a null next reference.

4. Suppose we are maintaining a collection C of elements such that, each time we add a new element
to the collection, we copy the contents of C into a new array list of just the right size. What is the
running time of adding n elements to an initially empty collection C in this case?