Homework 6

Details

1. For each of the following, give the simplest Θ(tight) bound possible. Assume all logs are base 2 unless specified otherwise.
   (e.g. your answer should be something like Θ(n²), not Θ(263 n²-198 n + 999).
   1. 13 n² log¹²(n) + n^2.0001
   2. 1,000 n³ + n⁵ + 1,000,000 n²
   3. n¹¹ + 5ⁿ + n¹⁰¹ log²⁰⁰(n) + 3ⁿ + 25,432,000 + 23 n + 13 n²
   4. 2ⁿ + 3ⁿ
   5. 12 n³ log(n) + 23 n² log⁵(n) - 988 n + 99
   6. 12 n³ + 23 n²-988 n + 99,000,000
   7. 4ⁿ + n⁵
   8. 32×2^log(n) +23 n
   9. (n² log(n) + n³)(n²+n+32)(2ⁿ+3ⁿ+n²+n+1+log(n))
   10. n²log₃(n)/ log₅(n) + 3 n²

2. Rank the following functions in increasing order of rate of growth. If two of them have the same growth rate, write them on the same line. Otherwise, put them one per line in increasing order of growth.
   1. n log(n)
   2. 453 n³
   3. 13 n³ + 27 n²-563 n + 67
   4. 2²ⁿ
   5. n²
   6. 3ⁿ
   7. 11 n log(n²)
   8. n^2.0001
   9. 4ⁿ
   10. 23 log₁₀(n)
   11. n² log(n)

3. For each of the following functions, give a simple tight bound for the best-case and the worst-case running times. Briefly justify your answers (That means you do not need to give a formal proof, but justify your answer somehow.). Assume A.length=n.

   1. int sumArray(int []A) {
          int sum=0;
          int i=0;
          while(i < A.length) {
              sum = sum + A[i];
      	i++;
      	if(sum>12345) {
                  i=A.length;
      	}
          }
          return sum;
      }
      

   2. int computeGruhop(int []A) {
          int sum=0;
          for(int i=0 ; i < A.length ; i++) {
              for(int j=0 ; j < A.length ; j++) {
                  sum = sum + A[i]*A[j];
      	    if(sum==1000000) {
                      i = A.length;
      	    }
      	}
          }
          return sum;
      }
      

   3. int anotherSum(int []A) {
          int sum=0;
          for(int i=0 ; i < A.length ; i++) {
              for(int j=0 ; j < 100 ; j++) {
                  sum = sum + A[j] + A[i];
      	}
          }
          return sum;
      }
      

   4. void HalfIt(int n) {
          while(n > 0) {
              n = n/2;
          }
      }
      

   5. // Assume A and B are both n by n.
      Matrix MatrixMultiply(Matrix A, Matrix B) {
          Matrix C;
          for(int i=0 ; i < n; i++) {
              for(int j=0 ; j < n ; j++) {
      	    C[i][j]=0;
                  for(int k=0 ; k < n ; k++) {
      		C[i][j] += A[i][k]*B[k][j];
      	    }
      	}
          }
          return C;
      }