Problem 3. Assume that your machine takes time(work), i + j to compare two elements in locations i and j. Analyze how much exact comparison time Bubble sort takes in the worst case to sort an array of size n. Assume that the array is stored in locations 1 to n. IMPORTANT: Consider the i+j specified in the problem as different from the i and j from the for loops of bubble sort. That is, the time needed to compare two elements is the sum of their locations in the array and is no longer just 1. You may assume regular bubble sort algorithm as discussed in the class:

for i = n downto 2 do for j = 1 to i-1 do if A[j] > A[j+1] then A[j] 4 end if end for end for A[j+1]