COT-4400: Design and Analysis of Algorithms

QUESTION 1

The algorithm below computes the maximum value in an array A[1..n] with n elements:

Which of the following is the correct loop invariant of the for loop?

		At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..i-1].
		At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..i].
		At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[1..n].
		At the start of each iteration i of the for loop, max contains the maximum value of the subarray A[0..i-1].

QUESTION 2

Arrange the following functions in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your list, then it should be the case that f(n) = O(g(n)).

question 3: