Consider the recursive algorithm given below: procedure bubblesort(n); var i,j…

Consider the recursive algorithm given below:

procedure bubblesort(n);

var i,j : index; temp : item;

begin

for i:=1 to n-1 do

if A[i] > A[i+1] then

begin temp := A[i]; A[i] := A[i+1]; A[i+1] := temp end;

bubblesort(n-1)

end

Let aₙ be the number of times the ‘if...then...’ Statement gets executed when the algorithm is run with value n. Set up the recurrence relation by defining aₙ in terms of aₙ₋₁. Solve for aₙ. Assume the recursion stops when n≤1.