Assignment 2

For each of the specifications below, write the algorithm in C in two ways: iteratively (ie using for/while loops) and recursively (ie no for/while/goto allowed!). Also, compute, showing all relevant details, the worst case time complexity of both your implementations. For each implementation, discuss the space complexity of the implementations [exact computations are better, but a heuristic discussion is acceptable].

• Finding the minimum value in an integer array
• Shell sort of an integer array
• Searching for a specific value in a sorted integer array
• Searching for a specific value in an unsorted integer array
• Computing the gcd of two positive integers using the Euclidean algorithm. [the complexity of this algorithm is a difficult problem]