[Solved] CECS328-hw4

Homework assignment 4:

• Suppose a machine on average takes 10^-8 seconds to execute a single algorithm step. What is the largest input size for which the machine will execute the algorithm in 2 seconds assuming the number of steps of the algorithm is T(n) = a. log n
  1. ⁿ
  2. n
  3. n²
  4. n³
  5. 2ⁿ

• For the machine in the previous example, how long will it take to run the algorithm for an input of size 1,000, assuming the time complexities from the same example?

• An algorithm takes 5 seconds to run on an input of size 100. How long will it take to run on an input of size 1000 if the algorithm has a running time that is linear? quadratic? log-linear? cubic?

• An algorithm is to be implemented and run on a processor that can execute a single instruction in an average of 10^-9 What is the largest problem size that can be solved in one hour by the algorithm on this processor if the number of steps needed to execute the algorithm is n, n², n³, log n? Assume n is the input size.

• Determine the asymptotic running time for the following piece of code, assuming that n represents the input size.

1. sum = 0;

for(i=0; i < n; i++)

sum++;

1. sum=0;

for(i=0;i<n;i++)

for(j=0; j< n*n;j++) sum++;

1. sum=0;

for(i=0;i<n;i++)

for(j=0; j< i;j++)

sum++;

1. sum = 0;

for(i=0; i < n; i++) for(j=0; j < i*i; j++)

for(k=0; k < j; k++)

sum++;

1. sum = 0;

for(i=0; i < n/2; i++)

for(j=0; j < (i*i)/2; j++)

sum++;

1. for(i=0; i < length(a) ; i++) binary_search(a, a[i]); //key = a[i]

1. for(i=0; i < n; i++) for(j=0; j < n; j++)

linear_search(a, key); //key is not in array, length(a) == n

• What is the largest value of n such that an algorithm whose running time is 10n² runs faster than an algorithm whose running time is 50n on the same machine?