Algorithm BubbleSort works by making repeated passes

QUESTION:

Algorithm BubbleSort works by making repeated passes through a list; on each pass, adjacent elements that are out of order are exchanged. At the end of pass 1, the maximum element has bubbled up to the end of the list and does not participate in subsequent passes. The following algorithm is called initially with j = n. BubbleSort(list L; integer j) //recursively sorts the items from 1 to j in list L into increasing order if j = 1 then sort is complete, write out the sorted list else for i = 1 to j 1 do if L[i] > L[i + 1] then exchange L[i] and L[i + 1] end if end for BubbleSort(L, j 1) end if end function BubbleSort Section 3.3 Analysis of Algorithms 215 a. Walk through algorithm BubbleSort to sort the list 5, 6, 3, 4, 8, 2. b. Write a recurrence relation for the number of comparisons of list elements done by this algorithm to sort an n-element list. c. Solve this recurrence relation.