Closed Books, Closed Notes Time: 40 minutes
Each question carries 30 pts.
Question 1 [6×5 points]
(i) Define the terms big-O, big-Ω and big-Θ notations.
1
(ii) Let α and β be real numbers such that 0 <α<β.
(a) Is nα in O(nβ)?
(b) Is nβ in O(nα)?
For (a) and (b), justify your answer.
3 (iii) Show that, if c is a positive real number, then g(n) = 1 + c + c2 + ··· + cn is:
• Θ(1) if c< 1.
• Θ(n) if c = 1.
• Θ(cn) if c> 1.
5
Question 2 [3×10 points]
Suppose you are choosing between the following three algorithms:
• Algorithm A solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and them combining the solutions in linear time.
• Algorithm B solves problems of size n by recursively solving two subproblems of size n − 1 and then combining the solutions in constant time.
• Algorithm C solves problems of size n by dividing them into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n2) time.
What are the running times of each of these algorithms (in big-O notation)? Show all your calculations as to how you arrived at that conclusion.
7
8 9
