CPSC170A
Fundamentals of Computer Science II

For each of the following functions give the big-O and big-Ω.

1. int pow(int base, int exponent) {
     power = 1;
     for (int i = 0; i < exponent; i++) {
       power *= base;
     }
     return power;
   }

2. int pow(int base, int exponent) {
     power = 1;
     for (int i = 0; i < exponent; i++) {
       for (int j = 0; j < base; j++) {
         power += base;
       }
     }
     return power;
   }

3. int pow(int base, int exponent) {
     if (exponent == 1) {
       return base;
     } else {
       return base * pow(base, exponent - 1);
     }
   }

4. int pow(int base, int exponent) {
     if (exponent == 1) {
       return base;
     else if (exponent % 2 == 0) {
       half_pow = pow(base, exponent / 2);
       return half_pow * half_pow;
     else {
       half_pow = pow(base, exponent / 2);
       return base * half_pow * half_pow;
     }
   }

Write the C++ function void merge_sort(int array[], int size) that sorts the array, in place, using the merge sort algorithm. The function should not use the Vector class. It can make a copy of a subset of the array when doing a merge.