Homework 1

Due Monday, February 16, at the start of class. Be sure to do both sides.

1. Compute the sum of the number of times the statements in the following code fragments are executed, expressing your answer as indicated (show your work). Count your answers carefully (there are 15 parts to this question) for full credit.
   1. Four answers: integers where n = 1, n = 2, n = 4, and n = 100

      s1    i = 0;
      s2    while (i < n)
      s3    {  for (int j = 0; j < n; j++)
      s4          cout << "Hello world";
      s5       i = i + 1;
            }
      

   2. One answer: an integer

      s1    for (int i = 1; i <= 6; i++)
      s2       for (int j = 1; j <= 10; j++)
      s3          cout << i * j << endl;
      s4    for (int k = 0; k < 1000; k++)
      s5       cout << "Hello" << end;
      

   3. One answer: in terms of n

      s1    cin >> n;
      s2    for (int i = 1; i <= n + 6; i++)
      s3       for (int j = 1; j <= n + 10; j++)
      s4          cout << i * j << endl;
      s5    for (int k = 1; k <= n + 1000; k++)
      s6       cout << "Hello" << end;
      

   4. Five answers: integers where n = 1, n = 4, n = 6, n = 7, and n = 8

      s1    while (n > 1)
      s2    {  cout <<  n << endl;
      s3       n = n / 2;
            }
      

   5. One answer: in terms of n

      s1    cin >> n;
      s2    for (i = 1; i <= n; i++)
      s3    {  temp = n;
      s4       while (temp > 0)
      s5       {  cout << n * temp << endl;
      s6          temp = temp / 2;
               }
            }
      

   6. Three answers: integers where q = 3, q = 2, and q = 10; x is the array {3, 6, 9, 4, 18, 10, 12, 1, 0, 16}

      s1    for ( i = 0; i < 10; i++)
      s2    {  if (q == x[i])
      s3       {  cout << "q is in the array at position " << i;
      s4          return;
               }
            }
      s5    cout << "q is not in the array"
      

2. For items (a), (c), (d), and (e) in question 1, give the running time in big-oh notation.

3. Write two program fragments labeled (A) and (B) such that (A) has a "better" run-time when expressed in big-oh notation but takes longer to run for a small input (say an input size of 10).

4. If a piece of code runs in time O(N²) and takes 2 minutes to run when N is 10,000 how long would you estimate the fragment would take to run when N=40,000? Why is your answer only an estimate?

5. If a piece of code runs in time O(N³) and takes 2 minutes to run when N is 10,000 how long would you estimate the fragment would take to run when N=30,000?