For the given algorithm below, answer the questions -

1. How many times in total line 3 is executed? Show your steps.

2. Suppose T(n) is the function you got from part 1. Prove (using the definition of big-O) that it is O( n^2 ). Show sufficient details of your work.

3. How many times in total line 4 is executed? Hint: You probably have to figure out the worst-case and best-case input first. Describe the best case and worst case inputs if needed and show sufficient details of your work.

4. (1pt for the correct inequality + 2 bonus points for the correct solution). Suppose T(n) is the function you got from part 1. Prove (using the definition of .) it is ( n^2 ). Show sufficient details of your work.

++++++

Input: a sequence A of n numbers.

Output: a sorted sequence of A

BSort(A, n)

1. for i = 1 to n-1
2. for j = n downto i+1
3. if A[j] < A[j-1]
4. exchange A[j] with A[j-1]