
1144 CHAPTER 15 Running Time Analysis
EXERCISES,PROBLEMS, AND PROJECTS
15.7 Exercises,Problems,and Projects
15.7.1 Multiple Choice Exercises
1. What is the Big-Oh of this function:
T(n) = n
2
- 2 n + 99
❑ O (n
2
)
❑ O (99)
❑ O (n)
❑ O (1)
2. What is the Big-Oh of this function:
T(n) = n
3
+ 10 n
2
+ 20 n + 30
❑ O (n
3
)
❑ O (n
2
)
❑ O (n)
❑ O (1)
3. What is the Big-Oh of this function:
T(n) = n
2
+ n * log n + 12 n + 5
❑ O (n * log n)
❑ O (n
2
)
❑ OO (n)
❑ O (1)
4. We have the following recurrence relation representing the running
time of a function; what is the running time of that function?
T(n) = T(n - 1) + 1
❑ O (2
n
)
❑ O (n * log n)
❑ O (n
2
)
❑ O (n)
4963X_CH15_Anderson.qxd 11/28/07 ...