22C:21: Computer Science II: Data Structures

Quiz 3: September 24, 2004


  1. For each of the five claims below, write down whether the claim if true or false.
    1. $8\log_{10} n + 9\log_5(n) = O(\log_2 n)$.

    2. True.
      Explanation: log's of different bases grow at the same rate.
    3. $8n^2 + 10 \cdot 2^n = O(n^2)$.

    4. False.
      Explanation: 2^n grows much faster than n^2 and dominates the expression.
    5. $3n + \frac{4n^2}{\ln(n)} = O(n)$.

    6. False.
      Explanation: n^2/ln(n) grows just a little slower than n^2, but much faster than n.
    7. $8n^2 + 9n\log(n) = O(n^2)$.

    8. True.
      Explanation: n^2 grows faster than n log(n).
    9. $3\sqrt{n} + 2\log(n) = O(\sqrt{n})$

    10. True.
      Explanation: sqrt(n) grows faster than log(n).

  2. The following is a recursive function that determines whether a given integer array is sorted or not. It is missing one line of code, which is a return statement in the recursive case of the code. Complete the function by supplying this missing line of code.
    public static boolean isSorted(int[] data, int n)
    {
    	// base case
    	if(n == 1)
    		return true;
    	else
    	{
    		// Recursive case
    		boolean temp = isSorted(data, n-1);
    	
    		// Here is the missing line of code
    		return (temp) && (data[n-2] <= data[n-1]);
    	}
    }