CS14 Assignment 1

Assigned: October 18th, 2001
Due: October 25th, 2001, in class

1. Prove that the following equalities are correct

a.  6n-4 = O(n)

b. n ²+5 = O( n² )

      c. 10n ² = O(n ³)

guideline: find c and n ₀ that satisfy the definitions

2. Prove that the following is false

n ² = O(n )

guideline: show that for any c, you can find an n that does not satisfy the definition.

3.    A and B are two programs that perform the same task.  A has running time 1000n , and B has running time 10n².  Find the range of n values for which program A is faster than program B.

4.    A and B are two programs that perform the same task.  A has running time 1000n log₂n, and B has running time n ².  Find the range of n values for which program A is faster than program B.

5.    A program stores n items in a sorted array.  Below is the code of a function for inserting a new number into the array, in its correct position.  Count is the number of items in the array before the new item is added.

 void insert(int array[], int & n, int newitem)
 {
    int pos = n-1;
    while (pos > 0 && newitem < array[pos-1])
    {
       array[pos] = array[pos-1];
       pos--;
    }
    array[pos] = newitem;
    n++;
 }

a. What is the best case for running this code segment (where does newitem need to go?)

      b. What is the operations count for the best case?  What is the order of magnitude (big-Oh)?

c. What is the worst case for running this code segment (where does newitem need to go?)

d. What is the operations count for the worst case?  What is the order of magnitude (big-Oh)?

*e. What is the average case for running this code segment (where does newitem need to go?)

*f. What is the operations count for the average case?  What is the order of magnitude (big-Oh)?

6.     A program to insert n numbers into a sorted array uses the insert function as follows

  count = 0;

    for (int i = 0; i < n; i++)
  {
     cin >> newitem;
     insert(array, count, newitem);
  }

a. assume the input to this program is already sorted.  How long does it take to run the program? (big-O is fine).
b. Assume the input to this program is reverse sorted.  How long does it take to run the program?
*c.  Assume the input to this program is random.  How long does it take to run?