Algorithms Weekly Test 01 PDF

# WEEKLY TEST - 01 ## Branch : CSE/IT ## Batch : Hinglish ## Subject : Algorithm ## Topic : Analysis of Algorithm ### Maximum Marks 15 **Q.1 to 5 Carry ONE Mark Each** **[MCQ]** 1. Sort the functions in increasing order of asymptotic (big O) complexity * f1(n) = n^0.999999 logn * f2(n...

# WEEKLY TEST - 01 ## Branch : CSE/IT ## Batch : Hinglish ## Subject : Algorithm ## Topic : Analysis of Algorithm ### Maximum Marks 15 **Q.1 to 5 Carry ONE Mark Each** **[MCQ]** 1. Sort the functions in increasing order of asymptotic (big O) complexity * f1(n) = n^0.999999 logn * f2(n) = 10000000n * f3(n) = 1.000001ⁿ * f4(n) = n² (a) f1(n), f2(n), f4(n), f3(n) (b) f3(n), f4(n), f2(n), f1(n) (c) f2(n), f4(n), f1(n), f3(n) (d) None of these **[MCQ]** 2. Sort the function in decreasing order of asymptotic (big O) complexity: - * f1(n) = 2^{2^1000000} * f2(n) = 2^1000000n * f3(n) = n√n (a) f2(n), f1(n), f3(n) (b) f3(n), f1(n), f2(n) (c) f1(n), f3(n), f2(n) (d) None of these **[MCQ]** 3. We know that O(g(n)) {f(n): There exist positive constant c and n₀ (Such that 0 ≤ f(n) ≤ c.g(n), for all n ≥ n₀ Given that f(n) = 10n² + 100 and g(n) = 2ⁿ; where n and n₀ are both positive integers. if c = 0.125 then for which value of n₀, f(n) = O(g(n))? (a) 12 (c) 14 (b) 13 (d) 15 **[MCQ]** 4. Suppose that there are 3 programs X1, X2 and X3 having time complexities f1(n), f2(n) and f3(n) respectively. Such that f₁(n) is O(f2(n)), f2(n) is O(f1(n)), f1(n) is O(f3(n)) and f3(n) is not O(f1(n)). Then which one of the statements is true from the following statements? (a) X3 is always faster than X1 and X2 for very large size inputs (b) X1 is faster than X2 and X3 for very large inputs (c) X3 is slower than X1 and X2 for very large input X2 is faster than X1 and X3 for very large size inputs (d) **[MCQ]** 5. Let f(n) = log log log √n and g(x) = 2³⁰³⁰³⁰ then which one of the following is true? * (i) f(n) = O(g(n)) * (ii) f(n) = Ω(g(n)) * (iii) f(n) = Θ(g(n)) * (iv) f(n) = ω(g(n)) (a) (i), (ii) and (iii) only (b) (ii), (iii) and (iv) only (c) (ii) and (iv) only (d) (iv) only **Q.5 to 10 Carry TWO Mark Each** **[MCQ]** 6. Consider the following code. ```c++ int a = 0; for(int x = 0; x < n; x++) { if (x%5==0){ for (int y = 0; y < n; y ++){ if (x == y) a+ = x * y) } } } ``` What is the highest asymptotic worst case time complexity of above code fragment? (a) O(n²) (c) O(n) (b) O(√n) (d) O(log n) **[MCQ]** 7. Arrange following function in the ascending order growth rate. * f1 = (1 + 0.0001)ⁿ, f2 = √n * f3 = (1.005)^√n, f₄ = (logn)^log√n * f₅ = (√n)^logn (a) f2, f5, f3, f4, f1 (b) f3, f4, f2, f5, f1 (c) f2, f5, f1, f3, f4 (d) None of the above **[MCQ]** 8. What is the time complexity of the following code ? ```c++ for (a = 0; a < n- 2; a ++) { for (b = 0; b < 100; b = b+2) { for (c = 1; c < 8*n; c ++) { } } } ``` What is the time complexity of above code? (a) O(logn) (c) O(n) (b) O(2ⁿ) (d) none of these **[NAT]** 9. How many of the following statements is/are false * (i) 10√n+logn = O(n) * (ii) √n+logn = O(logn) * (iii) √n+logn =0(n) * (iv) √n+logn = Ω(√n) **[MCQ]** 10. Consider the following recursion function P(n) ```c++ { if (n <= 0) return 1; else if (n% 2 == 0) return P(n-1); else return P(n-2); } ``` What is the time complexity of above code? (a) O(logn) (c) O(n) (b) O(2ⁿ) (d) none of these ### Answer Key 1. (a) 2. (d) 3. (d) 4. (c) 5. (c) 6. (a) 7. (a) 8. (b) 9. (2) 10. (c) ## Hints and Solutions 1. (a) The correct order of these functions is f1(n), f2(n), f4(n), f3(n). To see why, f1(n) grows asymptotically slower than f2(n), recall that for any c > 0, log n is O(n). Therefore, we have f1(n) = n^0.999999 logn = O(n^0.999999.n^0.000001) = O(n) = O(f2(n)) The function f2(n) is linear, while function f4(n) is quadratic, So f2(n) is O(f4(n)). Finally, we know that f3(n) is exponential, which grows faster than quadratic, So, f4(n) is O(f3(n)). 2. (d) The correct order of these functions is f2(n), f3(n), f1(n) in decreasing order. The variable n never appears in the formula f₁(n). So despite the multiple exponentials, fı(n) is constant. Hence it is asymptotically smaller than f3(n) which does grow with 'n'. f2(n) = 2^1000000n n = 1 f3(n) = n√n 2^1000000×1 > 1√1 n = 2 2^1000000×2 > 2√2 : .. f2(n) > f3(n) Option (a), (b), (c) are not correct option. So, f2(n) f3(n) f1(n) is correct decreasing order. Hence option (d) is correct. 3. (d) Given C = 0.125 f(n) ≤ C.g(n) 10n² + 100 ≤0.125 × 2ⁿ We need to check from n = 1 to 15 So, if n = 15 10 * (15)² + 100 ≤ 0.125 × 2¹⁵ 2250+100 ≤ 0.125 × 32768 2350 ≤4096 (True) 4. (c) Given, f1(n) = O(f2(n)) f2(n) = O(f1(n)) f1(n) = O(f3(n)) f3(n) ≠ O(f1(n)) The above functions conclude that, growth of f3 is larger than the growth rate of f1 and f2. 5. (c) x3 is slower than x1 or x2. f(n) = log log log√n, g(n) = 2²⁰²⁰²⁰ f(n) = Ω(g(n) because g(n) is constant and f(n) is depending on 2, therefore it is correct. f(n) ≠ O(g(n)) because f(n) is greater than g(n) f(n) = w(g(n)) because f(n) > g(n),Correct. 6. (a) (ii) and (iv) are true. The inner most loop (if statement) executes per loop, we must check x = = y is true one per each iteration. This will take some non-zero constant amount of time. So the innermost loop will perform approximately n work. The outer most loop and if statement will perform 'n' work during only 1/5th of the iteration and will perform a constant amount of wort in the remaining 4/5th of the time. So, total amount of work done is approximately n 4n n+ 1 5 5 ... T(n) = 5 n² 4n + 5 4 7. (a) As we can see f1 and f3 are similar so lets compare these first. f₁ = (1 + 0.0001)ⁿ f3 = (1.005)^√n ... By seeing n and √n in exponents we can conclude that f1 > f3 Now comparing f2, f4, and f5 log n f2 =(√n) logn log√n f4 = (10 logn)` , taking log √, taking log √n log(logn) £5 =( (√n)logn 2 gn²log(n) taking log Form above we can clearly see that f5 > f2 and f4 > f5 because of √n>logn ........(b) Now comparing f1 and f2 (1 + 0.0001)<sup>n</sup> = (√) log n Taking log on both sides we get n log 1.001 = logn log √n By comparing above we can clearly say that 'n' of f1 will always be greater and n makes greater than f2. .. f1 > f2 and similarly f5 > f1 .....(c) .....(d) also, f₁ > f4 solving by using log....(e) ... from (a), (b), (c), (d) and (e) We can conclude that .. f2 f5 f3 f4 f1 is correct answer. 8. (b) * `a` ranging from 0 to n - 2 in first loop so it is O(n) * `b` is ranging from 0 to 100 which is constant time in 2nd (inner loop) so O(1) * `c` is ranging from 1 to 8 n inner loop so it is O (n) n*1* n which is n² ... O(n²), so option (b) is correct. 9. (2) * (i) 10√n+logn=O(n) Correct, because ..√n <n * (ii) √n+logn = O(logn) incorrect because √n>logn * (iii) √n + log n = 0(n) incorrect it should be O(n) or 0(log) * (iv) √n+logn=0√n, Correct 10. (c) One of P(n-1) of P(n-2) will be called, In worst case T(n) = T(n-1) + O(1) T(n) = 0(n)