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-O for execution time? Determine a formula that expresses the height of the tree. What is the Big-O for memory? Recursion Tree:

bubbleSort

|

v

sort(array, 0)

|

v

bubble(array, 0, 3)

|

v bubble(array, 0, 2)

|

v bubble(array, 0, 1)

|

v bubble(array, 0, 0)

|

v sort(array, 1)

|

v bubble(array, 1, 3)

|

v

bubble(array, 1, 2)

|

v

bubble(array, 1, 1)

|

v

sort(array, 2)

|

v

bubble(array, 2, 3)

|

v

bubble(array, 2, 2)

|

v

sort(array, 3)