CS 477/677 Assignment 2

Due date: September 15, 2005, 11:30 AM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.
  1. List the following functions in order of increasing asymptotic complexity. If two or more functions have the same asymptotic complexity, say so.
    1. n + log2n
    2. n2
    3. 5n2+n-17
    4. log2n
    5. log10n
    6. 2log2n
    7. n log n
    8. log log n
    9. n0.00001
    10. 2n
    11. (1.00001)n
    12. The nth Fibonacci number
    13. log(n!)
    14. n!
  2. For each of the following code or pseudo-code fragments, write a recurrence for the time complexity in terms of n, and then solve that recurrence. Assume that all variables have type integer. (See these problems, together with answers, for help.)
    1. proc george(n)
      while n > 0
      {
      write('I cannot tell a lie. I chopped down the cherry tree.');
      n = n-1;
      }
    2. proc martha(n)
      while n > 0
      {
      george(n);
      n = n-1;
      }
    3. proc anthony(n)
      if n > 0
      {
      george(n);
      anthony(n/2);
      }
    4. proc cleopatra(n)
      if n > 0
      {
      anthony(n);
      cleopatra(n/2);
      cleopatra(n/2);
      }

    5. proc bozo(n)
      if n > 0
      {
      write('Hi there, folks!');
      bozo(n-1);
      bozo(n-1);
      }

Back to Course Page