CS 232

Homework #2

Due, Wednesday, February 7, in class

1. You have been hired as a consultant by NextCoolThingOnTheWeb, Inc.  They perform certain computations for their clients.  The good news is that business is brisk.  The bad news is that they are worried that they have so much business that they may need to buy a new computer.  Their computation times grow as N³.  Currently, they take 0.05 seconds to process 1000 items.  They are willing to have their clients wait up to ten seconds for an answer.  They need to know how many items they can process on their current computer and still meet this customer goal.  Determine this number for them. 
   
   
2. For each of the following blocks of code, give the best possible time estimate.  (Note: choose your notation carefully.)
   
   
   1. for(i=1; i<n; i++) {
         for(j=1; j<n; j*=2) {
            sum++;
         }
      }
      
   
   
   2. for(i=1; i<n; i*=2) {
         for(j=1; j<i; j++) {
            sum++;
         }
      }
      
   
   
   3. for(i=1; i<n; i++) {
         for(j=1; j<n/2; j+=2) {
            sum++;
         }
      }
      
   
   
   4. for(i=1; i<n; i*=2) {
         for(j=1; j<i; j++) {
            sum++;
         }
      }
      
   
   
   5. for(i=1; i<n; i*=2) {
         for(j=1; j<i; j*=2) {
            sum++;
         }
      }
      

3. Express the running time of the sequential search and binary search algorithms using recurrence relations as done in class for the various sorting algorithms.