Last name: _____________________
Given name: ____________________
CSE373 Winter 2005
Miniquiz #2
January 21, 2005
1. Suppose that
f(n) = O(g(n))
but
g(n) != O(f(n))
A very informal way of expressing this is that (pick one)
A. f is more efficient than g
B. g is more efficient than f
C. f and g are equally good (or equally bad)
2. When analzying code, the formula that results should be
a function of some parameter which reflects the "size" of the
problem. In the following code, which of the variables is the
best candidate for that parameter?
for (int b = a; b < a*2; b++) {
int c = b*b;
System.out.println("b=" + b + " c=" + c);
}
A. a
B. b
C. c
3. Given these three functions:
n log(n)
n2
2n
Rank them in order from best (fastest) to worst
A. n log(n), 2n, n2
B. 2n, n2, n log(n)
C. n log(n), n2, 2n
E. n2, n log(n), 2n
4. With reference to the definition of Big O (as given in class
Wednesday), show that
n = O(n/3)
by finding a c and an n 0 which satisfy the
definition.