CISC 3220

Assignment #2, Due: Monday, September 19.

1. List the following functions from highest to lowest asymptotic order. Indicate if any are of the same order.
   2ⁿ
   lg n
   n²
   (lg n)²
   sqrt(n)
   n lg n
   n
   n!
   n³ + log n
   6
   n - n² + 5n³
   
   
2. Part a: Given 3 distinct integers, write an algorithm to find the median of the 3 integers.
   Part b: Describe D, which is the set of all possible inputs into your algorithm. In particular, you should list all possible inputs, in terms of the given problem. Then, compute the number of operations done in each case.
   Parb c: Choose the worst case input in part b and tell what the worst case time complexity of your algorithm is. Take the average of all inputs in part b for the average case time complexity.
   Part d: Try to prove a lower bound for finding the median of three numbers.
   
   
   
   
3. (a) Is 2ⁿ⁺¹ = O(2ⁿ)? Justify.
   (b) Is 4ⁿ = O(2ⁿ)? Justify.
4. Let f(n) = .5n³, g(n) = 4n² + 2n . For what values of n is f(n) <= g(n) ? What does your answer have to do with the definitions of O and OMEGA?
5. If f(n) = O(g(n)) and h(n) = O(g(n)),
   
   a. Is it always true that f(n)=h(n)?
   b. Is it always true that f(n) = O(h(n))?
   c. Is it always true that f(n) = THETA(h(n))?
   
   Justify your answers - either explain why it is true, or give an example to show that it is false.
6. Prove that THETA defines an equivalence relation on the functions. (Hint: recall that an equivalence relation must be reflexive, symmetric, and transitive.)
7. This Web page provides a visual comparison of various running times.
   1. Enter the value 5 and see how long the various running times take.
      Why does the cubic loop take longer than the exponential and factorial loops?
   2. Now enter the value 10.
      How do the cubic, exponential and factorial running times compare now?
   3. What does this have to do with asymptotic order?