Furthermore, please note that the graders will grade 2 out of the 4 questions randomly. Therefore, if the grader decides to check questions 1 and 4,and you haven’t answered question 4, you’ll lose points for question 4. Hence, please answer all the questions.
1. Prove or disprove the following assertions: (8+8+9)
(i) If f(n) = O(g(n)) then log2f(n) = O(log2g(n))
(ii) If f(n) = O(g(n)) then 3f(n) = O(3g(n))
(iii) If f(n) = O(g(n)) then f(n)3 = O(g(n)3)
2. Algorithm A1 takes 10−4×2n seconds to solve a problem instance of size n and Algorithm A2 takes 10−2×n3 seconds to do the same on a particular
machine. (8+8+9)
(i) What is the size of the largest problem instance A2 will be able solve in one year ?
(ii) What is the size of the largest problem instance A2 will be able solve in one year on a machine one hundred times as fast ?
(iii) Which algorithm will produce results faster, in case we are trying tosolve problem instances of size less than 20 ?
3. Prove or disprove the following with valid arguments: (8+8+9) (i) 3n3 + 1000 = O(n2).
(ii) 2n2log(n) = Θ(n2).
(iii) 3nn4 + 8 ∗ 4nn3 = O(3nn4).
1
4. Take the following list of functions and arrange them in ascending orderof growth rate. That is, if function g(n) immediately follows f(n) in your list, then it should be the case that f(n) is O(g(n)). (25)
(i) f1(n) = n4.6.
(ii) f2(n) = (2n)1.6.
(iii) f3(n) = n4.5 + 87. (iv) f4(n) = 40n.
(v) f5(n) = 120n
2
