Algorithm Analysis and Design
First Exam, Spring 2018/2019
March 17th 2019
Instructor: Dr. Khaled W. Mahmoud
Student Name: ________________________
Student Number: ______________________
Major: _______________________________
Question
Points
Score
1
25
2
35
3
40
Total
100
Question 1: Asymptotic Notations [25 Points]
(a) [10 pts] For each pair of functions below, determine which function grows asymptotically faster then
give all the θ, O and Ω relations that apply. You only need to mention the relations in which f(n)
appears on the left-hand side.
(i) f(n) = log(n!), g(n) = log(nn)
(ii) f(n) = logkn g(n) = nɛ, k≥1, ɛ>0
F(n) = θ, O and Ω (g(n))
Logarithmic vs polynomial
F(n) = O (g(n))
(iii) f(n) = 2n g(n) = 2n/2
Take log for both sides
F(n) = Ω (g(n))
