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
- Bubble sort of an integer array
- Searching for a specific value in a sorted integer array (using the smart algorithm!)
- 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!]
For some bonus marks, you can compute either best-case time
complexity (ie lower bound) or even better, average case time
complexity. Be precise about the meaning of your answer.