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 of disprove the following with valid arguments: (5+5+5+5+5) (i) n!∈ O(nn).
(ii) 2n22n + nlog(n) ∈ Θ(n22n).
(iii) 10n2 + 9 = O(n).
(iv) n2log(n) = Θ(n2).
(v) n32n + 6n23n = O(n32n).
2. Suppose that you have algorithms with the size running times listed below.Assume that these are the exact number of operations performed as a function of the input size n. Suppose you have a computer that can perform 1010 operations per second, and you need to compare a result in at most an hour of computation. For each of the algorithms, what is the largest input size n for which you would be able to get the result within an
hour? (6+6+6+7)
(i) n2.
(ii) n3.
1
(iii) 50n2. (iv) 3n.
3. Algorithm A1 takes 10−3×2n seconds to solve a problem instance of size n and Algorithm A2 takes 10−2×n4 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?
4. Take the following list of functions and arrange them in ascending order of 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.5.
(ii) f2(n) = (3n)0.6.
(iii) f3(n) = n4 + 20. (iv) f4(n) = 25n.
(v) f5(n) = 260n
2
