variable #D1 = 6, #D2 = 5, #D5 = 3

1. Asymptotic Notations (a) [4] For each of the following statements indicate whether it is true or false. i. (2000 * #D2)n + 0.5n log n + 20 = o(n log n) ii. 2n? +(3+100 * #D5)n +45 = 12 (n log n) (b) [6] Algorithms A and B have running time TA(n) and TB(n), respectively. Con- sider the following statements: Algorithm A is faster than Algorithm B. Algorithm B is faster than Algorithm A. There is not enough information to determine which algorithm is faster. Which of the above statements is true as n becomes very large in each of the following cases? Justify your answer. In the following, a = #D1 + 2, B = #D2 + 2. i. TA(n) = (n2); Te(n) = O(n2a) ii. TA(n) = O(n); Te(n) = 2(n log n) iii. TA(n) = 0(n2+B); TB(n) = 12(n+8V log n)