CS 1704 Fall 2003 Homework 7 Answers

 Q  A     Reason
------------------------------------------------------------------------------------
For questions 1 through 5, you just need to apply the theorem in the course notes
that sets out the big-O ordering of the most common function categories:

 1  5     
 2  4
 3  3
 4  5     You need to multiply this one out to clearly see the dominant term.
 5  7
 
 6  5     The body of the outer loop is executed N times, as i counts down from N
          to 1 ( and exits when i reaches 0).
          On each pass through the body of the outer loop, the body of the for 
          loop is executed i times where i is the value of the outer loop counter.
          The cost of executing the inner loop body is constant, as are the costs
          of the remaining statements in the body of the outer loop.  Since all
          constants are equivalent in big-O terms, we may view the cost of the
          code fragment as:
          
                    Sum of 1 from i = N down to 1
                    
         From the summation formulas in the notes, this is O(N^2).
 
 7  4    In this case, the inner loop is executed the same number of times on
         each pass through the body of the outer loop.  But, since the counter
         for the inner loop is doubled on each pass, how many passes does the
         inner loop make?  Well, assume N = 2^k, then j takes on the values:
         
            j:  1  2  2^2  2^3  2^4 .... 2^k
 
         so the inner loop runs k times where k == log N.
         
         The outer loop makes N passes, so the total cost is N * log N.

The instructions do not specify just HOW the linked list is to be searched.
However, there is only one defensible choice:  a linear search.  The fact that
the linked list is sorted does not buy us much efficiency.

 8  1    Best case is clearly that the item sought is at the front of the list.
 
 9  3    Worst case is that the item sought is at the end of the list (or not
         in the list at all).  Either way, the whole list must be searched and
         that will take N comparisons.

10  3    If each element is equally likely to be the target then on average
         a search would go halfway down the list, taking N/2 comparisons.

11  2    The question is equivalent to the inequality:  T(N) / 10^6 <= 60.
         From there, it's just algebra:
         
               T(N)             <= 60,000,000
               2N^2 + 7N/2 + 42 <= 60,000,000
               2N^2 + 7N/2 - 58,999,958 <= 0
              
         Using the quadratic formula, we find the larger root is approximately
         5431.

12  4    The time would be T(N) / 10^6.  If N == 2^20, then

            T(2^20) == 2^20 log 2^20 + 7 * 2^20 + 42
                    == 2^20 * 20 + 7 * 2^20 + 42
                    == 27 * 2^20 + 42
                    == 28311594
                    
         So the number of seconds would be about 28.3.

13  7    Repeating the logic from question 12:

            T(2^21) == 2^21 log 2^21 + 7 * 2^21 + 42
                    == 2^21 * 21 + 7 * 2^21 + 42
                    == 28 * 2^21 + 42
                    == 58720298
  
         So the number of seconds would be about 58.7.

14  7    Same logic, different formula:

            T(2^20) == (2^20)^2 + 2 * 2^20 + 1
                    == 2^40 + 2^21 + 1
                    == 1099513724929

         So the number of seconds would be about 1099513.7; since there
         are 86400 seconds in a day, this works out to about 12.7 days.

15  9    Same logic, different input size:

            T(2^21) == (2^21)^2 + 2 * 2^21 + 1
                    == 2^42 + 2^22 + 1
                    == 4398050705409

         So the number of seconds would be about 4398050.7; since there
         are 86400 seconds in a day, this works out to about 50.9 days.
         
         Note:  there is a point here.  With N log N cost, doubling the
         size of the input doesn't do much more than double the time
         required.  With N^2 cost, doubling the size of the input 
         increased the time by a factor of about four.