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 (^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

(^2). Show sufficient details of your work.

++++++

Input: a sequence A of n numbers.

Output: a sorted sequence of A

BSort(A, n)

for i = 1 to n-1

for j = n downto i+1

if A[j] < A[j-1]

exchange A[j] with A[j-1]