Homework 2

Due Monday, February 10, at the start of class.

1. Use the formal definition of Big O notation to show that 2X³ + X is O(X³).
2. 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).
3. What is the run-time of the following fragment expressed in big-oh notation as a function of its input n?

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

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?
6. What is the run-time of the following fragment expressed in big-oh notation as a function of its input n?

   cin >> n;
   for ( i=1; i<=n; i++ )
   {  temp = n;
      while ( temp > 0 )
      {  cout << n * temp << endl;
         temp = temp / 2;
      }
   }