CS410, Summer 1998			Name:
Quiz #1
July 1

Consult no sources.  Put your answers below (obviously).

1. Formally, what does it mean for f(n) to be O(g(n))?

2. Let f(n) = n^3 + 4n^2. True or false:
a) f(n) is O(n^2)
b) f(n) is O(n^2 log n)
c) f(n) is O(n^3)
d) f(n) is O(n^3 log n)

ANSWERS
=======

1. By definition, f(n) is O(g(n)) if there exist constants c and n_o such that 
f(n) <= cg(n) for all n > n_o.

Grading: 4 points.  
	No points taken off for using < instead of <= or vice-versa.  
	2 points taken off for not explaining that c and n_o are constants.  
	2 points taken off for switching an inequality (> instead of <).
	2-3 points taken off for giving a correct but informal definition
	1 point taken off for minor weirdnesses.

	Full credit for giving the textbook definition (in terms of sets).

2. False, False, True, True

Grading: 1.5 points each, no partial credit.