Recursion and add preconditions and postconditions

1.     Consider the following iterative function:

int square(int n) {   int result = 0;   for (int i = 1; i <= n; i++)     result += 2 * i - 1;   return result; }

Rewrite the function _square using recursion and add preconditions and postconditions as comments. Then prove by induction that the recursive function you wrote is correct.

2.     Suppose the number of steps required in the worst case for two algorithms are as follows: 

•        Algorithm 1: f(n) = 3n² + 9

•        Algorithm 2: g(n) = 51n + 17

Determine at what integer value of n, algorithm 2 becomes more efficient than algorithm 1.

3.     Given the following function that sorts an array of values:

void bubbleSort(double[] array) {   for (int i = 0; i < array.length; i++)     for (int j = array.length - 1; j > i; j--)       if (array[j] < array[j - 1])         swap(array, j, j - 1); }

Let n be the length of the array. Using summation evaluation, determine the number of swaps that are performed in the worst case as a function of n. 

4.     Given the following recursive function and it corresponding helper function that returns the sum of all the elements of an array that are located at even subscripts:

int sumEvenElements(int array[], int i) {   if (i >= array.length)     return 0;

  return  array[i] + sumEvenElements(array, i+2);

} 

int sumEvenElements(int array[]) {     return sumEvenElments(array, 0) }

Assume n is the length of the array. Find the initial condition and recurrence equation that expresses the execution time for the worst case of the recursive function and then solve that recurrence.