Name:________________________________________

1. (1 pt) True or False: For every function f and g, if f(n) = O(g(n)), then f(n) = Omega(g(n)).
   
   
   
   
2. (1 pt) True or False: For every function f and g, if f(n) = Theta(g(n)), then f(n) = Omega(g(n))
   
   
   
   
3. (2 pts) What is the recurrence relation to describe the worst-case running time of a recursive algorithm that breaks the problem up into 4 pieces, each of which is half the size of the original input, makes a recursive call on each of the 4 pieces, and does a linear amount of additional work?
   
   
   
   
4. (1 pt) True or False: n^e = o(log n), where e = .00001.