Exam 1 Sample Questions
  1. log_2 8 = ?
  2. log_b a * log_a b = ?
  3. What does it mean to say that f(n) dominates g(n)?
  4. f(n) = 3n^2 + 2n + 13
    f(n) is in O(?)
  5. Is f(n) = sqrt(n^5) in O(n^2)?
  6. How does Big-Theta differ from Big-O?
  7. If f(n) is in O(n) and g(n) is in O(n),
    then (f(n) - g(n) ) in O(?)?
  8. Give a running time (T_n) for the following code fragment : 
    	for (int i = 0; i < n ; i ++){
	   for (int j=0; j < n; j++){
		loop body
	   }
	}
  9. T_n = 4T(n/3) + n^2. Solve for the asymptotic running time using the "Master Method".
  10. Write the pop() method for the contiguous-memory implementation of a stack.