Homework 1 Solution

CS409 - Spring 2000

Due: Thursday, Feb 3

1. (10 pts) Rank the following functions by order of growth. That is, find an arrangement g₁,g₂,...,g_n of the functions satisfying g₁ = O(g₂), g₂ = O(g₃), etc.

   n log n, n³, 3ⁿ, n/(log n), sqrt(n), log(log n), log n, (log n)², (log n)sqrt(n), n²log n.

   Arranged in order:
   log(log n), log n, (log n)², sqrt(n), (log n)sqrt(n), n/(log n), n log n, n²log n, n³, 3ⁿ.

2. (10 pts) Problem 1.8 in text.
   If y has n digits in base b then y is of size at most bⁿ.  So we need to add x to itself at most bⁿ times.  Each addition takes time O(n); note that the numbers get longer as you do more additions, but longest number you'll see is of length 2n since that's the maximum length of the final product.  So the total time spent is O(nbⁿ).

    

3. (10 pts) Problem 1.3 in text.
   1. Yes, it's possible.  The algorithm can be fast on some inputs without affecting the worst-case time bound.
   2. Well, yes, this is possible.  Basically it means that your proof is not as good as you'd like.  A big-O bound is just an upper bound; the algorithm can actually be faster.
   3. Yes, it's possible.  The algorithm can be fast on some inputs without affecting the worst-case time bound.
   4. No, this is impossible.  A worst-case bound of Q(n²) means that there is at least one input (the worst-case one) that has to use up time proportional to n².
   5. Yes.  One can show that 19n² < f(n) < 101n² for n sufficiently large.  Thus, be definition, f(n) = Q(n²).

    

4. (10 pts) Fill in the table below with the worst-case time for each operation. Use big-O notation and write your time bound in terms of n, the current number of items in the data structure.  The operations are insert (place a new item in the data structure), getMin (return the value of the minimum item in the data structure and delete it), and reportMax (return the value of the maximum item in the data structure without deleting it).  Determine the best time bound that you can without changing the data structure.  Note that you can use O(1) extra space if it helps achieve a better bound (if you use extra space, explain how you're using it).

   Data Structure	insert	getMin	reportMax
   sorted array	O(n)	O(1)	O(1)
   unsorted array	O(1)	O(n)	O(1)
   sorted linked list	O(n)	O(1)	O(1)
   unsorted linked list	O(1)	O(n)	O(1)

We can handle reportMax in O(1) time if we keep an extra variable to hold the current maximum; this max can be updated during insert in O(1) time.  We can keep track of the current min in the same way, so reporting the min is easy, but we run into trouble trying to make a fast getMin because of the deletion part of the operation: for an unsorted structure, we would have to search the structure in order to update the current min.