Question 1: (6 marks) Consider the given functions bellow. Sort all of them using the asymptotic order (big-O). Provide short explanation for your answer.
3 log n
3 log log n
nlog n
5n
nn1=4
(n4 )n=4
Question 2: (4 marks) Among the following given functions, which one(s) is (are) representing the time complexity of a sub-quadratic algorithm. Explain your answer, and give a polynomial as an example for each part.
3
O(n2 )
3
(n2 )
nO( 32 )
n ( 32 )
Question 3: (5 marks) (From the DPU textbook, Exercise 1.4) Show that
log(n!) = (n log n):
(Hint: To show an upper bound, compare n! with nn. To show a lower bound, compare it with (n=2)n=2. )
Question 4: (10 marks) Asymptotically analyze the running time of the following algorithm.
1
2
