Exercise 1 (25 points)

This exercise explores the concept of best, average, and worst cases for the time complexity. Consider the following problem: findNumberInList

Input: a number a, and a sequence A containing n numbers (not necessarily sorted)

Output: an integer i (1 to n) that is the position of a in Sequence A

a) Propose in pseudocode an algorithm for findNumberInList.

b) Propose an action to analyze the time complexity of findNumberInList

c) Is the time complexity constant (the same) for any problem instance? If not, determine and justify the time complexity for the best, average, and worst cases.

d) How does each of the time complexities for the best case, average case, and worst case grow?

e) Analyze the space complexity. Is your algorithm in-place?