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. .

2. True.
Explanation: log's of different bases grow at the same rate.
3. .

4. False.
Explanation: 2^n grows much faster than n^2 and dominates the expression.
5. .

6. False.
Explanation: n^2/ln(n) grows just a little slower than n^2, but much faster than n.
7. .

8. True.
Explanation: n^2 grows faster than n log(n).

9. 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]);
}
}