Shown below is the code for the bubble sort consisting of two recursive methods that

replace the two nested loops that would be used in its iterative counterpart:

void bubbleSort$($int array$[])\{$

sort$($array$,0)$;

$\}$

void sort$($int$[]$ array, int i$)\{$

if $($i $<$ array.length $-1)\{$

bubble$($array$,$ i$,$ array.length $-1)$;

sort$($array$,$ i $+1)$;

$\}$

$\}$

void bubble$($int$[]$ array, int i$,$ int j$)\{$

if $($j $<=$ i$)$

return;

if $($array$[$j$]<$ array$[$j $-1])\{$

int temp $=$ array$[$j$]$;

array$[$j$]=$ array$[$j $-1]$;

array$[$j $-1]=$ temp;

$\}$

bubble$($array$,$ i$,$ j $-1)$;

$\}$

Draw the recursion tree for bubbleSort when it is called for an array of length $4$ with

data that represents the worst case. Show the activations of bubbleSort, sort and

bubble in the tree. Explain how the recursion tree would be different in the best case.

$2.$ Refer back to the recursion tree you provided in the previous problem. Determine a

formula that counts the numbers of nodes in that tree. What is Big$-$ for execution time?

Determine a formula that expresses the height of the tree. What is the Big$-$ for memory?