Computer Science 3650
Spring 2020
January 31 Class Exercises

1. (courtesy of Dr. Abrahamson)
   Suppose that f(n) = 2n² + n. Which of the following is true, and which is false?

   1. f(n) is O(n).
   2. f(n) is O(n²).
   3. f(n) is O(n³).
   4. f(n) is O(2ⁿ).
   5. f(n) is Ω(n).
   6. f(n) is Ω(n²).
   7. f(n) is Ω(n³).
   8. f(n) is Ω(2ⁿ).
   Answers
   

2. For n ≥ 2, order the following functions of n in increasing magnitude.

   1. n³
   2. 2ⁿ
   3. n lg n
   4. n²
   5. n
   6. lg n
   7. n!
   Answer