This is an algorithm problem.

For the following problem stated as pseudo-code, let A[l. . . r ] denote the sublist of the integer list A from the l-th to the r-th element, inclusive.

Three(A[l. . .n]) {

If n 1 Then Return;

InsertionSort(A[l . . . n]);

Three(A[l . . . ]);

Three(A[ + 1 . . . ]);

Three(A[ + 1 . . . n]);

}

a) State a recurrence that gives the complexity T(n) for algorithm Three.

b) Find the tight complexity of algorithm Three with prove.