DAA-vfyjvtfjtfvfvfthjccghcdhrtchgdT&S_C.pptx

nothing norma

1. 1. What is the time, and space complexity of the following code: int a = 0, b = 0; for (i = 0; i < N; i++) { a = a + rand(); } for (j = 0; j < M; j++) { b = b + rand(); } Options: O(N * M) time, O(1) space O(N + M) time, O(N + M) space O(N + M) time, O(1) space O(N * M) time, O(N + M) space

2. 1. What is the time, and space complexity of the following code: int a = 0, b = 0; for (i = 0; i < N; i++) { a = a + rand(); } for (j = 0; j < M; j++) { b = b + rand(); } Options: O(N * M) time, O(1) space O(N + M) time, O(N + M) space O(N + M) time, O(1) space O(N * M) time, O(N + M) space Answer:- 3) O(N + M) time, O(1) space

3. 2. What is the time complexity of the following code: int a = 0; for (i = 0; i < N; i++) { for (j = N; j > i; j--) { a = a + i + j; } } Options: O(N) O(N*log(N)) O(N * Sqrt(N)) O(N*N)

4. 2. What is the time complexity of the following code: int a = 0; for (i = 0; i < N; i++) { for (j = N; j > i; j--) { a = a + i + j; } } Options: O(N) O(N*log(N)) O(N * Sqrt(N)) O(N*N) Answer:- 4. O(N*N)

5. 3. What is the time complexity of the following code: int i, j, k = 0; for (i = n / 2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n / 2; } } Options: O(n) O(N log N) O(n^2) O(n^2Logn)

6. 3. What is the time complexity of the following code: int i, j, k = 0; for (i = n / 2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n / 2; } } Options: O(n) O(N log N) O(n^2) O(n^2Logn) Answer: 2. O(nLogn)

7. 4. What does it mean when we say that an algorithm X is asymptotically more efficient than Y? Options: X will always be a better choice for small inputs X will always be a better choice for large inputs Y will always be a better choice for small inputs X will always be a better choice for all inputs

8. 4. What does it mean when we say that an algorithm X is asymptotically more efficient than Y? Options: X will always be a better choice for small inputs X will always be a better choice for large inputs Y will always be a better choice for small inputs X will always be a better choice for all inputs Answer: 2. X will always be a better choice for large inputs

9. 5. What is the time complexity of the following code: int a = 0, i = N; while (i > 0) { a += i; i /= 2; } Options: O(N) O(Sqrt(N)) O(N / 2) O(log N)

10. 5. What is the time complexity of the following code: int a = 0, i = N; while (i > 0) { a += i; i /= 2; } Options: O(N) O(Sqrt(N)) O(N / 2) O(log N) Answer: 4. O(log N) /// Explanation: We have to find the smallest x such that ‘(N / 2^x )< 1 OR 2^x > N’ x = log(N)

11. 6. Which of the following best describes the useful criterion for comparing the efficiency of algorithms? Time Memory Both of the above None of the above

12. 6. Which of the following best describes the useful criterion for comparing the efficiency of algorithms? Time Memory Both of the above None of the above Answer: 3. Both of the above

13. 7. How is time complexity measured? By counting the number of algorithms in an algorithm. By counting the number of primitive operations performed by the algorithm on a given input size. By counting the size of data input to the algorithm. None of the above

14. 7. How is time complexity measured? By counting the number of algorithms in an algorithm. By counting the number of primitive operations performed by the algorithm on a given input size. By counting the size of data input to the algorithm. None of the above Answer: 2. By counting the number of primitive operations performed by the algorithm on a given input size.

15. 8. What will be the time complexity of the following code? for (int i = 1; i < n; i++) { i *= k; } O(n) O(k) O(log k n) O(log n k)

16. 8. What will be the time complexity of the following code? for (int i = 1; i < n; i++) { i *= k; } O(n) O(k) O(log k n) O(log n k) Answer: 3. O(log k n)

17. 9. What will be the time complexity of the following code? int value = 0; for(int i=0;i<n;i++) for(int j=0;j<i;j++) value += 1; n (n+1) n(n-1)/2 n(n+1)

18. 9. What will be the time complexity of the following code? int value = 0; for(int i=0;i<n;i++) for(int j=0;j<i;j++) value += 1; n (n+1) n(n-1)/2 n(n+1) Answer: 3. n(n-1)/2

19. 10. Algorithm A and B have a worst-case running time of O(n) and O(logn), respectively. Therefore, algorithm B always runs faster than algorithm A. True False

20. 10. Algorithm A and B have a worst-case running time of O(n) and O(logn), respectively. Therefore, algorithm B always runs faster than algorithm A. True False Answer: False /// Explanation: The Big-O notation provides an asymptotic comparison in the running time of algorithms. For n < n ​​, algorithm A might run faster than algorithm B, for instance.

21. What is the time complexity of the following code? Cpp for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // Some O(1) operation } } O(N * M) O(N + M) O(N) O(M)

22. What is the time complexity of the following code? Cpp for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // Some O(1) operation } } O(N * M) O(N + M) O(N) O(M) Answer: O(N * M)

23. What is the space complexity of the following code? cpp int arr[100]; for (int i = 0; i < N; i++) { arr[i] = i; } O(N) O(1) O(N^2) O(log N)

24. What is the space complexity of the following code? cpp int arr[100]; for (int i = 0; i < N; i++) { arr[i] = i; } O(N) O(1) O(N^2) O(log N) Answer: O(N)

25. What is the time complexity of this recursive function? cpp int recursiveFunc(int n) { if (n <= 1) return 1; return recursiveFunc(n - 1) + recursiveFunc(n - 1); } O(n) O(2^n) O(n^2) O(log n)

26. What is the time complexity of this recursive function? cpp int recursiveFunc(int n) { if (n <= 1) return 1; return recursiveFunc(n - 1) + recursiveFunc(n - 1); } O(n) O(2^n) O(n^2) O(log n) Answer: O(2^n)

27. What is the time complexity of the following code? cpp int a = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { a++; } } O(N) O(N^2) O(N^3) O(N log N)

28. What is the time complexity of the following code? cpp int a = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { a++; } } O(N) O(N^2) O(N^3) O(N log N) Answer: O(N^2)

29. What is the space complexity of this code? cpp void function(int n) { int arr[n]; // Some operations } O(n) O(1) O(log n) O(n^2)

30. What is the space complexity of this code? cpp void function(int n) { int arr[n]; // Some operations } O(n) O(1) O(log n) O(n^2) Answer: O(n)

31. What is the time complexity of this algorithm? cpp for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Some operation } for (int k = 0; k < M; k++) { // Some operation } } O(N^2 + M) O(N * M) O(N^2 + N * M) O(N + M)

32. What is the time complexity of this algorithm? cpp for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Some operation } for (int k = 0; k < M; k++) { // Some operation } } O(N^2 + M) O(N * M) O(N^2 + N * M) O(N + M) Answer: O(N^2 + M)

33. What is the time complexity of the following code snippet? cpp int count = 0; for (int i = 1; i <= n; i *= 2) { count++; } O(n) O(log n) O(1) O(n log n)

34. What is the time complexity of the following code snippet? cpp int count = 0; for (int i = 1; i <= n; i *= 2) { count++; } O(n) O(log n) O(1) O(n log n) Answer: O(log n)

35. What will be the time complexity of this code? cpp for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { // Some operation } } } O(N^3) O(3N) O(N^2) O(log N)

36. What will be the time complexity of this code? cpp for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { // Some operation } } } O(N^3) O(3N) O(N^2) O(log N) Answer: O(N^3)

37. Which of the following statements about time complexity is true? Time complexity only considers the worst-case scenario. Time complexity can be expressed in terms of Big-O notation. Time complexity is always linear. Time complexity does not depend on input size.

38. Which of the following statements about time complexity is true? Time complexity only considers the worst-case scenario. Time complexity can be expressed in terms of Big-O notation. Time complexity is always linear. Time complexity does not depend on input size. Answer: Time complexity can be expressed in terms of Big-O notation.

39. What is the space complexity of this algorithm that uses a stack to reverse a string? cpp void reverseString(string& str) { stack<char> s; for (char c : str) { s.push(c); } for (int i = 0; i < str.length(); i++) { str[i] = s.top(); s.pop(); } } O(1) O(n) O(log n) O(n^2)

40. What is the space complexity of this algorithm that uses a stack to reverse a string? cpp void reverseString(string& str) { stack<char> s; for (char c : str) { s.push(c); } for (int i = 0; i < str.length(); i++) { str[i] = s.top(); s.pop(); } } O(1) O(n) O(log n) O(n^2) Answer: O(n)